Probabilistic Turing machine

A probabilistic Turing machine , abbreviated to PTM, is a concept from theoretical computer science . It is a Turing machine that also has the ability to control its computational paths by means of a random experiment .

definition

With a probability of ½, the program unit decides at each step about the transition function to be used

A probabilistic Turing machine is a Turing machine that has two transition functions instead of one transition function and selects the first or the second transition function for each calculation step by means of a B (½) random experiment. If the Turing machine finally stops on an input , then the result is 0 (rejection of ) or 1 (acceptance of ). ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle x}$

This is based on the idea that there are two possible transitions for each calculation step, that is, two possibilities to write a character, to define the next state and to execute the next read / write head movement. Which of the two options is chosen depends on chance. The result of the calculation is therefore random; a second run of the machine on the same input data can lead to a different result.

In particular, the running time of a calculation can depend on the random selection of the transition function. The running time of a probabilistic Turing machine is therefore defined as follows: If a function, then one says that the probabilistic Turing machine M has running time if M holds on the input in every possible calculation in at most steps, where the length of the input is. ${\ displaystyle T: \ mathbb {N} \ rightarrow \ mathbb {N}}$ ${\ displaystyle T}$ ${\ displaystyle x}$ ${\ displaystyle T (| x |)}$ ${\ displaystyle | x |}$

Delimitations

Deterministic Turing machine

Deterministic Turing machines can be viewed as a special case of a probabilistic Turing machine. For this purpose, the two transition functions must be the same, because then each calculation step is independent of the choice of transition function and thus of the outcome of the random experiment and the machine behaves like a deterministic Turing machine with this one transition function.

Nondeterministic Turing machine

The nondeterministic Turing machine is also characterized by two transition functions, but it does not have the possibility of a random experiment. In the case of the nondeterministic Turing machine, one rather imagines that both options are selected for each computation step, so that the machine goes through every possible path by continually branching. The question then arises whether there is a path that leads to acceptance, that is, has the result 1. In a probabilistic Turing machine, one actually uses the result of the random calculation or examines the probabilities with which a result is achieved.

Robustness in terms of probability

The question arises as to how the computer model presented here behaves if one replaces the probability ½ of the B (½) random experiments with another probability 0 <p <1. If the machine can only carry out B (p) experiments, it can also carry out B (½) random experiments using the following trick that goes back to John von Neumann . The B (p) experiments are carried out in pairs until the two components of the double experiment are different; the result of the first component is then chosen as the result. One can show that this leads to a B (½) experiment. Therefore, all calculations of a probabilistic Turing machine can also be carried out with one for which "only" B (p) experiments for a fixed 0 <p <1 are possible instead of B (½) experiments.

The question of whether one can also produce B (p) experiments using a probabilistic Turing machine is somewhat more difficult. That is certainly not possible for non-computable p. However, moderate conditions at p make it possible to carry out B (p) experiments with constant additional effort using B (½) experiments. It is sufficient that there is a polynomial and a deterministic Turing machine that calculates the i-th decimal place of the binary representation of p in time . ${\ displaystyle f}$ ${\ displaystyle f (i)}$

Complexity classes

Since randomized algorithms are relevant in practice, it makes sense to define complexity classes using probabilistic Turing machines.

If a function and a language are said to be decided by a probabilistic Turing machine M in time , if M stops after every input after at most steps and . It is the result of 0 or 1 of the bill of the machine M on input , 1 or 0, depending on whether or not, and the probability refers to the universe of all possible bills. ${\ displaystyle T: \ mathbb {N} \ rightarrow \ mathbb {N}}$ ${\ displaystyle L \ subset \ {0.1 \} ^ {*}}$ ${\ displaystyle L}$ ${\ displaystyle T}$ ${\ displaystyle x \ in \ {0.1 \} ^ {*}}$ ${\ displaystyle T (| x |)}$ ${\ displaystyle \ textstyle P (M (x) = L (x)) \ geq {\ frac {2} {3}}}$ ${\ displaystyle M (x)}$ ${\ displaystyle x}$ ${\ displaystyle L (x)}$ ${\ displaystyle x \ in L}$ ${\ displaystyle P}$

${\ displaystyle \ mathrm {BPTIME} (T (n))}$ is the set of all languages that can be decided in time by a probabilistic Turing machine . There is particular interest in the set of languages that can be decided in polynomial time by a probabilistic Turing machine, so one defines ${\ displaystyle T}$

{\ displaystyle \ mathrm {BPP} = \ bigcup _ {c \ in \ mathbb {N}} \ mathrm {BPTIME} (n ^ {c})}

.

Another important application is the definition of the complexity class IP of the interactive proof systems , which leads to an equivalent characterization of the complexity class PSPACE .

Individual evidence

^ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Section 7.1: Probabilistic Turing Machines
^ John von Neumann: Various techniques used in connection with random digits , Applied Math Series (1951), Volume 12, pages 36-38
^ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Lemma 7.12
^ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , definition 7.2

[1] Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Section 7.1: Probabilistic Turing Machines

[2] John von Neumann: Various techniques used in connection with random digits , Applied Math Series (1951), Volume 12, pages 36-38

[3] Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Lemma 7.12

[4] Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , definition 7.2