| 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)
|
| has 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)