probabilistic Turing machine

A

Published in Phillip A. Laplante, Dictionary of Computer Science, Engineering, and Technology, 2017

alternating Turing machine a nondeterministic Turing machine having universal states, from which the machine accepts only if all possible moves out of that state lead to acceptance. See also model of computation, nondeterministic Turing machine, oracle Turing machine, probabilistic Turing machine, universal Turing machine.

Reflections on probabilistic compared to quantum computational devices

View Article

Journal Information

Published in International Journal of Parallel, Emergent and Distributed Systems, 2021

Giuseppe Corrente

A probabilistic Turing machine (PTM), on a finite set Q of states and the finite alphabet Γ, is given by a transition function δ: Γ × Q × Γ × Q × {L, N, R} → [0, 1] such that if (σ∗, q∗) ∈ Γ × Q, then

probabilistic Turing machine

Explore chapters and articles related to this topic

A

Reflections on probabilistic compared to quantum computational devices