| dbo:abstract
|
- En teoria de la complexitat, s'utilitzen Màquines de Turing probabilística per definir diferents classes de complexitat. Una 'Màquina de Turing probabilística és una màquina de Turing, en concret de la forma no determinista, que selecciona aleatòriament entre les transicions disponibles a cada punt amb idèntica probabilitat per cada alternativa. Alternativament, es pot definir també com una màquina de Turing determinista amb una instrucció addicional "escriure" on el valor de l'escriptura està uniformement distribuït en l'alfabet de la màquina. Com a conseqüència, una màquina de Turing probabilística pot (a diferència d'una màquina de Turing) tenir un resultat estocàstic: donada una entrada i un programa per la màquina, pot executar el programa en temps variables d'execució, o pot no parar, o més encara, pot acceptar una entrada en una execució, i no acceptar-la en la següent. Es desprèn que l'acceptació d'una cadena d'entrada d'una màquina de Turing probabilística pot ser definida de diferents maneres. I a aquestes formes d'acabar corresponen diferents classes de complexitat que inclouen , , i . Al restringir-se la màquina a usar tan sols espai logarítmic en lloc de temps polinòmic, es pot definir les classes anàlogues , , i ZPL. En incloure ambdues restriccions s'obtenen les classes , , i . Els són un altre model de càlcul que és inherentment probabilístic. (ca)
- Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik. Es handelt sich um eine Turingmaschine, die zusätzlich die Fähigkeit hat, ihre Rechenwege durch ein Zufallsexperiment zu steuern. (de)
- En komputebleca teorio, probableca maŝino de Turing estas speco de maŝino de Turing kiu hazarde elektas inter la haveblaj trairoj je ĉiu punkto kun egala probablo. Ekvivalente, ĝi povas esti difinita kiel determinisma maŝino de Turing havanta aldonan skriban komandon ĉe kiu la valoro skribita estas unuforme distribuita en la maŝina alfabeto (ĝenerale, egala verŝajneco de skribo de '1' aŭ '0' sur la bendo). Alia komuna varianto estas simple determinisma maŝino de Turing kun aldona bendo plena de hazardaj bitoj, nomata kiel la hazarda bendo. Sekve de tio, probableca maŝino de Turing povas (malsimile al determinisma maŝino de Turing) havi rezultojn; sur donita enigo kaj komanda stata maŝino, ĝi povas havi malsamajn rultempojn, aŭ ĝi povas ne halti ajn; plui, ĝi povas akcepti enigon en unu rulo kaj malakcepti la saman enigon en la alia rulo. Pro tio la nocio de akcepto de linio per probableca maŝino de Turing povas esti difinita en malsamaj manieroj. Estas diversaj polinomo-tempaj hazardigitaj kiuj rezultiĝas de malsamaj difinoj de akcepto - RP, Co-RP, BPP kaj . Se oni limigas la maŝinon al anstataŭ polinoma tempo, rezultiĝas la analogaj , Co-RL, kaj . Se fari ambaŭ limigojn, rezultiĝas klasoj , Co-RLP, , kaj . Probableca kalkulado estas ankaŭ kritika por la difino de plejparto klasoj de interagaj pruvaj sistemoj, en kiu la kontrolila maŝino dependas sur hazardo por eviti estado aŭgurita kaj artifikita per la ĉiopova provata maŝino. Ekzemple, la klaso egalas al , sed se hazardo estas forprenita de la kontrolilo, rezultiĝas nur , kiu estas ne sciata sed larĝe kredita al esti konsiderinde pli malgranda klaso. Unu el la centraj demandoj de komplikteorio estas ĉu hazardo aldonas povon; tio estas, ĉu estas problemo kiu povas esti solvita en polinoma tempo per probableca maŝino de Turing sed ne per determinisma maŝino de Turing? Aŭ ĉu povas determinismaj maŝinoj de Turing kompetente simuli ĉiujn probablecajn maŝinojn de Turing kun maksimume polinoma malplirapidiĝo? Nun estas larĝe kredite de esploristoj ke la lasta estas la okazo, kiu devus enhavi ke P = BPP. La sama demando por logaritma spaco anstataŭ polinoma tempo (ĉu L = BPLP?) estas eĉ pli larĝe kredita al esti vera. Aliflanke, la pova hazardo donas al interagaj pruvaj sistemoj kaj la simplaj algoritmoj ĝi kreas por malfacila problemoj kiel polinomo-tempa primeca provado kaj logaritmo-spaca sugestas ke hazardo povas aldoni povon. (eo)
- En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad. Una Máquina de Turing probabilística es una Máquina de Turing, en concreto de la forma no determinista, que selecciona aleatoriamente entre las transiciones disponibles en cada punto con idéntica probabilidad para cada alternativa. Alternativamente, se puede definir también como una máquina de Turing determinista con una instrucción adicional “escribir” donde el valor de la escritura está uniformemente distribuido en el alfabeto de la máquina. Como consecuencia, una máquina de Turing probabilística puede (a diferencia de una máquina de Turing) tener un resultado estocástico: Dada una entrada y un programa para la máquina, puede ejecutar el programa en tiempos variables de ejecución o puede no parar; más aún, puede aceptar una entrada en una ejecución y no aceptarla en la siguiente. Se desprende que la aceptación de una cadena de entrada en una máquina de Turing probabilística puede ser definida de varias formas. Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen , . y . Al restringirse la máquina a solo usar espacio logarítmico en lugar de tiempo polinómico, se definen las clases análogas , , , y ZPL. Al incluir ambas restricciones se obtienen las clases , , y . Los computadores cuánticos son otro modelo de cálculo que es inherentemente probabilístico. (es)
- In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution. In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines having an additional "write" instruction where the value of the write is uniformly distributed in the Turing Machine's alphabet (generally, an equal likelihood of writing a "1" or a "0" on to the tape). Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits called the "random tape". A quantum computer is another model of computation that is inherently probabilistic. (en)
- En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour les algorithmes probabilistes comme le test de primalité de Miller-Rabin. (fr)
- 確率的チューリング機械（かくりつてきチューリングきかい、英: Probabilistic Turing machine）は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。 各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット（一般に '1' と '0'）についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。 結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。 従って、確率的チューリング機械での文字列の受理/不受理は、通常とは異なった形で定義される。この定義の違いによって、様々な多項式時間の確率的な複雑性クラスが生じる。例えば、RP、Co-RP、BPP、ZPP などである。制約を多項式時間ではなく対数領域とした場合は、LP、Co-RL、BPL、ZPL がある。また、両方を制約を課した場合は、RLP、Co-RPL、BPLP、ZPLP がある。 確率的計算は対話型証明系の多くのクラスの定義においても重要である。この場合、検査機構（verifier）は全能の証明機構（prover）にだまされないためにランダム性を必要とする。例えば、IPクラスは PSPACE に等しいが、検査機構でのランダム性を排除すると NP と等しくなってしまう。PSPACE と NP の関係は正確には未だ確定していないが、おそらく NP の方が小さいと考えられている。 計算複雑性理論の課題の1つとして、「ランダム性は計算能力を向上させるか?」という問題がある。つまり、確率的チューリング機械で多項式時間で解ける問題があるとき、それが決定性チューリング機械では多項式時間で解けないと言えるだろうか? それとも、決定性チューリング機械で確率的チューリング機械をシミュレートして、高々多項式程度の低速化で問題を解けるだろうか? 現在、多くの研究者は後者（P = BPP）が正しいと考えている。多項式時間ではなく対数領域についての同様の問題（L = BPLP か?）は、さらに広く信じられている。一方、ランダム性によって対話型証明系の能力が与えられ、難しい問題を解く単純なアルゴリズムがランダム性の導入によって発見されているのも事実である。 本質的に確率的な計算のモデルとして、量子コンピュータがある。 (ja)
- 확률적 튜링 기계(Probabilistic Turing machine)는 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을 가진다. 확률적 튜링 기계는 일반적인 튜링 기계를 확장하여, '난수'라는 명령어를 추가한 것으로 구성할 수 있는데, 기계가 '난수' 명령어를 실행하면 테이프에는 0이나 1 중 하나가 균등한 확률로 적힌다. 또는 튜링 기계에 일반적인 테이프와 별도로 '난수 테이프'를 추가한 것으로도 구성할 수 있다. (ko)
- Nella teoria della calcolabilità, una macchina di Turing probabilistica è una macchina di Turing non deterministica che sceglie a caso fra le transizioni disponibili in ogni fase secondo una determinata distribuzione di probabilità. Si può perfino restringere questa definizione a una macchina che sceglie a ogni passo tra due transizioni con una probabilità 1/2 per ciascuna.. Nel caso di uguali probabilità per le transizioni, può essere definita come una macchina di Turing deterministica che ha un'istruzione di "scrittura" aggiuntiva dove il valore della scrittura è distribuito uniformemente nell'alfabeto della macchina di Turing (generalmente, una uguale probabilità di scrivere un "1" o uno "0" sul nastro). Un'altra formulazione comune è semplicemente una macchina di Turing deterministica con un nastro aggiunto pieno di bit casuali e chiamato perciò nastro casuale.. Come conseguenza, una macchina di Turing probabilistica (diversamente da una macchina di Turing deterministica) può avere risultati stocastici; su una data entrata e un dato stato di istruzione, la macchina può avere tempi di esecuzione diversi, o può non arrestarsi affatto; inoltre, può accettare un input in un'esecuzione e rifiutare lo stesso input in un'altra esecuzione. Perciò la nozione di accettazione di una stringa da parte di una macchina di Turing probabilistica può essere definita in modi diversi. Le varie classi di complessità randomizzate in tempo polinomiale che risultano da diverse definizioni di accettazione includono RP, co-RP, BPP e ZPP. Se restringiamo la macchina allo spazio logaritmico invece che al tempo polinomiale, otteniamo l'analogo , co-RL, e ZPL. Se applichiamo entrambe le restrizioni, otteniamo , co-RLP, e . La computazione probabilistica è critica, anche per la definizione della maggior parte delle classi dei , nei quali la macchina verificatrice dipende dalla casualità per evitare di essere prevista e ingannata dalla potentissima macchina dimostratrice. Ad esempio, la classe è uguale a PSPACE, ma se la casualità è rimossa dal verificatore, ci resta solo NP, che non è conosciuta, ma è largamente ritenuta essere una classe considerevolmente più piccola. Una delle questioni centrali della teoria della complessità è se la casualità aggiunga potenza; ossia, c'è un problema che può essere risolto in tempo polinomiale da una macchina di Turing probabilistica ma non da una macchina di Turing deterministica? O possono le macchine di Turing deterministiche simulare in maniera efficiente tutte le macchine di Turing probabilistiche con al massimo un rallentamento polinomiale? Quest'ultimo caso sembrerebbe il più realistico, il che implicherebbe P = BPP. La stessa domanda per lo spazio logaritmico invece del tempo polinomiale (è L = BPLP?) è ritenuta vera ancora più largamente. D'altro canto, la potenza che la casualità dà ai sistemi di prova interattivi, come pure ai semplici algoritmi che crea per problemi difficili come i test di primalità in tempo polinomiale e i test di connettività dei grafi nello spazio logaritmico, suggerisce che la casualità potrebbe aggiungere potenza. Un computer quantistico è un altro modello di computazione che è intrinsecamente probabilistico. (it)
- Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade. No caso de probabilidades iguals para as transições, esse tipo de máquina pode ser definido como uma máquina de Turing determinística tendo uma instrução adicional "write" onde o valor de escrita é uniformemente ditribuído no alfabeto da máquina de Turing (geralmente, uma probabilidade igual de escrever um '1' ou um '0' na fita). Outra reformulação comum é simplesmente uma máquina de Turing determinística com uma fita adicional repleta de bits aleatórios, chamada fita aleatória. Como consequência, uma máquina de Turing probabilística pode, ao contrário de uma máquina determinística, ter resultados estocásticos; numa dada entrada e instruções, ela pode ter diferentes tempos de execução ou pode até não parar; além disso, ela pode aceitar uma entrada numa execução e rejeitar a mesma entrada em outra. Então, a noção de aceitação de uma cadeia por uma máquina de Turing probabilística pode ser definida de maneiras diferentes. Várias classes de tempo polinomial aleatórias que resultam de diferentes definições de aceitação incluem RP, , BPP e ZPP. Se restringirmos a máquina para espaço logarítmico ao invés de tempo polinomial, nós obtemos as análogas RL, , BPL e ZPL. Se nós reforçarmos ambas as restrições, nós obtemos , , e . Computação probabilística também é crítica para a definição da maioria das classes de sistemas de provas interativos, nos quais a máquina verificadora depende de aleatoriedade para evitar ser prevista e enganada pela toda-poderosa máquina de prova. Por exemplo, a classe IP é igual a PSPACE, mas se aleatoriedade é removida do verificador, somos deixados apenas com NP, que não se tem certeza, porém acredita-se que é uma classe consideravelmente menor. Uma das questões centrais da teoria da complexidade é se aleatoriedade adiciona poder; isto é, há algum problema que pode ser resolvido em tempo polinomial por uma máquina de Turing probabilística, mas não por uma máquina de Turing determinística. Ou podem máquinas de Turing simular com eficiência todas as máquinas de Turing probabilística com um atraso no máximo polinomial? Atualmente acredita-se abertamente que a última afirmação é o caso, o que implicaria em P = BPP. A mesma questão para espaço logarítmico ao invés de tempo polinomial (L = BPLP?) é até mais abertamente aceita como verdade. Por outro lado, o poder que aleatoriedade dá para sistemas de prova interativos e os algoritmos simples que ela cria para problemas difíceis, tal qual teste de primalidade em tempo polinomial e teste de conectividade de grafos em espaço logarítmico sugerem que aleatoriedade, de fato, pode adicionar poder.Um computador quântico é outro modelo computacional é outro modelo que é inerentemente probabilístico. (pt)
- Обобщение детерминированной машины Тьюринга, в которойиз любого состояния и значений на ленте машина может совершить один из нескольких (можно считать без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки) Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью. Существует также альтернативное определение: Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом. Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP. (ru)
- 在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變(transition)。 在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面佈滿了許多隨機位元值的確定型圖靈機。 所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止； 甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。 因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。 同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了 RP，Co-RP，BPP and ZPP。 如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和。如果我們同時限制兩者，則有了，Co-RLP，，和。 隨機計算對於定義大多數的交互式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。 例如說，這個類別等同 PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。 複雜度理論的其中一個重點問題是：是否隨機性增加了演算法的能力？ 換句話說，是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出 P = BPP。相同問題的對數空間(log space)版本(是否L = BPLP?)則比起多項式時間版本更被廣泛相信為真。另外，隨機性給予交互式證明系統的力量，以及對困難問題所能建立更簡單的演算法的特質，例如多項式時間內的質數測試(primality testing)和對數空間的圖相連測試(graph connectedness testing)，又隱含著隨機性是有可能增加計算能力的。 量子計算機則是另一種先天就具有著機率性質的計算模式。 (zh)
|
| rdfs:comment
|
- Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik. Es handelt sich um eine Turingmaschine, die zusätzlich die Fähigkeit hat, ihre Rechenwege durch ein Zufallsexperiment zu steuern. (de)
- En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour les algorithmes probabilistes comme le test de primalité de Miller-Rabin. (fr)
- 확률적 튜링 기계(Probabilistic Turing machine)는 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을 가진다. 확률적 튜링 기계는 일반적인 튜링 기계를 확장하여, '난수'라는 명령어를 추가한 것으로 구성할 수 있는데, 기계가 '난수' 명령어를 실행하면 테이프에는 0이나 1 중 하나가 균등한 확률로 적힌다. 또는 튜링 기계에 일반적인 테이프와 별도로 '난수 테이프'를 추가한 것으로도 구성할 수 있다. (ko)
- En teoria de la complexitat, s'utilitzen Màquines de Turing probabilística per definir diferents classes de complexitat. Una 'Màquina de Turing probabilística és una màquina de Turing, en concret de la forma no determinista, que selecciona aleatòriament entre les transicions disponibles a cada punt amb idèntica probabilitat per cada alternativa. Alternativament, es pot definir també com una màquina de Turing determinista amb una instrucció addicional "escriure" on el valor de l'escriptura està uniformement distribuït en l'alfabet de la màquina. (ca)
- En komputebleca teorio, probableca maŝino de Turing estas speco de maŝino de Turing kiu hazarde elektas inter la haveblaj trairoj je ĉiu punkto kun egala probablo. Ekvivalente, ĝi povas esti difinita kiel determinisma maŝino de Turing havanta aldonan skriban komandon ĉe kiu la valoro skribita estas unuforme distribuita en la maŝina alfabeto (ĝenerale, egala verŝajneco de skribo de '1' aŭ '0' sur la bendo). Alia komuna varianto estas simple determinisma maŝino de Turing kun aldona bendo plena de hazardaj bitoj, nomata kiel la hazarda bendo. (eo)
- En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad. Una Máquina de Turing probabilística es una Máquina de Turing, en concreto de la forma no determinista, que selecciona aleatoriamente entre las transiciones disponibles en cada punto con idéntica probabilidad para cada alternativa. Alternativamente, se puede definir también como una máquina de Turing determinista con una instrucción adicional “escribir” donde el valor de la escritura está uniformemente distribuido en el alfabeto de la máquina. (es)
- In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution. (en)
- Nella teoria della calcolabilità, una macchina di Turing probabilistica è una macchina di Turing non deterministica che sceglie a caso fra le transizioni disponibili in ogni fase secondo una determinata distribuzione di probabilità. Si può perfino restringere questa definizione a una macchina che sceglie a ogni passo tra due transizioni con una probabilità 1/2 per ciascuna.. Un computer quantistico è un altro modello di computazione che è intrinsecamente probabilistico. (it)
- 確率的チューリング機械（かくりつてきチューリングきかい、英: Probabilistic Turing machine）は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。 各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット（一般に '1' と '0'）についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。 結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。 本質的に確率的な計算のモデルとして、量子コンピュータがある。 (ja)
- Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade. Como consequência, uma máquina de Turing probabilística pode, ao contrário de uma máquina determinística, ter resultados estocásticos; numa dada entrada e instruções, ela pode ter diferentes tempos de execução ou pode até não parar; além disso, ela pode aceitar uma entrada numa execução e rejeitar a mesma entrada em outra. (pt)
- Обобщение детерминированной машины Тьюринга, в которойиз любого состояния и значений на ленте машина может совершить один из нескольких (можно считать без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки) Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью. Существует также альтернативное определение: (ru)
- 在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變(transition)。 在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面佈滿了許多隨機位元值的確定型圖靈機。 所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止； 甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。 因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。 同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了 RP，Co-RP，BPP and ZPP。 如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和。如果我們同時限制兩者，則有了，Co-RLP，，和。 量子計算機則是另一種先天就具有著機率性質的計算模式。 (zh)
|
