Probabilistic Turing machine

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. A probabilistic Turing machine is a type of nondeterministic Turing machine in which each nondeterministic step is a "coin-flip", that is, at each step there are two possible next moves and the Turing machine probabilistically selects which move to take. A probabilistic Turing machine can be formally defined as the 7-tuple , where is a finite set of states is the input alphabet is a tape alphabet, which includes the blank symbol # is the initial state is the set of accepting (final) states is the first probabilistic transition function. is a movement one cell to the left on the Turing machine's tape and is a movement one cell to the right. is the second probabilistic transition function. At each step, the Turing machine probabilistically applies either the transition function or the transition function . This choice is made independently of all prior choices. In this way, the process of selecting a transition function at each step of the computation resembles a coin flip.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (10)

Related courses (7)

Related lectures (32)

Probabilistic Turing machine

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

CS-459: Foundations of probabilistic proofs

Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science, as well as on real-world secure systems. They underlie delegation of computation protocols a

MATH-642: Artificial Life

We will study the emergence of life-like phenomena, such as locomotion, resilience,, reproduction, and evolution in mathematical models, in particular in discrete and continuous cellular automata, dev

Elements of Computational Complexity PHYS-641: Quantum Computing

Introduces computational complexity, decision problems, quantum complexity, and probabilistic algorithms, including NP-hard and NP-complete problems.

Quantum Computation Delegation

Explores fully classical qubits, blind quantum computing, and verifiability in quantum delegation protocols.

Undecidability: Part 1

Introduces undecidability in recursive languages and Turing machines, showing languages without algorithmic recognition.