In Turing machines, “each instruction of a Turing machine is deterministic: Given the internal state and the symbol being scanned, the immediate next operation is wholly and uniquely determined.”(Kim 2011, p.143).

However, probabilistic automation is not deterministic. This means that

“the current internal state of the machine and the symbol it is scanning do not—do not always, at any rate—together uniquely determine what the machine will do next.” (Kim 2011, p.144).

What is being meant here by probabilistic automation in Turing Machines?

Does it mean, that there can be multiple ways a Probabilistic Automata can solve a complex problem? That one cannot determine how the automata will solve the problem, but one can only calculate the probability of the automata’s method of reaching the outcome?


Kim, J. (2011) Philosophy of mind [electronic resource] / Jaegwon Kim. 3rd ed. Boulder, CO: Boulder, CO : Westview Press.

  • Please read Wikipedia's Probabilistic Turing machine:"a probabilistic Turing machine can (unlike a deterministic Turing Machine) have stochastic results... is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is currently widely believed by researchers that the latter is the case, which would imply P = BPP."
    – Conifold
    Oct 28 '18 at 21:07

See Probabilistic Turing machine :

is a non-deterministic Turing machine which 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; on a given input and instruction state machine, it may have different run times, or it may not halt at all; further, it may accept an input in one execution and reject the same input in another execution.


On the other hand a turing machine can run a program that we cannot determine its "behavior" not because it is not deterministic but because we find it extremely difficult to understand either because it is complex but also because we didnt understand the implications of the program when we programmed it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.