A probabilistic Turing machine uses independent choices, as said in Wikipedia.

At each step, the Turing machine probabilistically applies either the transition function $\delta_1$ or the transition function $\delta_2$. This choice is made independently of all prior choices.

I am wondering what will happen if we break the requirement of independence.

Maybe it is clearer to reformulate it as a Turing machine with an added random tape. We may define a possibly correlated probabilistic Turing machine as an 8-tuple $M = (Q, \Sigma, \Gamma, q_0, A, \delta_0, \delta_1, D)$, where the first seven entries are as standard and $D$ is a distribution of bit tapes. Before the runtime, the machine samples a bit-tape $r$ from $D$. And at the $i$-th step, the machine uses $r_i$, the $i$-th bit of the sampled tape to choose which transition function to use, i.e., the machine uses $\delta_{r_i}$ for the $i$-th step.

Let $D$ be the uniform distribution of bit-tapes where each bit is independently uniform. It is a standard probabilistic Turing machine.

I think this more general notion, possibly correlated probabilistic Turing machine, may bring more computational power. Is there any paper or discussion about this?

  • 1
    $\begingroup$ I think you'll need to narrow this down. Just saying that the choices might not be independent leaves open too many possibilities, and as a result the question is too broad. For instance, it leaves open that every choice is actually made by omniscient space aliens, and then you're actually asking about the computational power of omniscient space aliens. In this way such a machine can emulate just about any conceivable model of computation. $\endgroup$
    – D.W.
    Apr 6, 2023 at 6:04
  • $\begingroup$ @D.W. You're right. Let's say that the choices are generated from a randomness source that is unaware of the definition and execution of the Turing machine. In other words, a new choice is sampled from a distribution conditioned and only conditioned on the choices made earlier. $\endgroup$ Apr 6, 2023 at 6:17
  • 1
    $\begingroup$ Thank you for your response. Please don't provide clarifications in the comments. Instead, edit your question to improve it based upon the feedback you've received. I don't know what "unaware of" means or what condition you are trying to impose; you'll need to formalize that and make your assumption more precise. $\endgroup$
    – D.W.
    Apr 6, 2023 at 6:19
  • $\begingroup$ @D.W. I edited and tried to formalize my question. Do you think it is clear enough? $\endgroup$ Apr 6, 2023 at 7:46

1 Answer 1


Suppose that $D$ always yields the same value, with probability 1: namely, the value of Chaitin's constant. Then such a machine is basically equivalent to a Turing machine with oracle access to Chaitin's constant, and can solve the halting problem and some other undecidable problems (see here). Or, as another example, such a machine can compute Chaitin's constant, whereas an ordinary Turing machine cannot. Therefore, in this case, your model offers additional computational power.

Suppose that sampling from $D$ is computable (on an ordinary probabilistic Turing machine). Then such a machine can be simulated, to arbitrary accuracy, by an ordinary probabilistic Turing machine. So, in some sense, your model offers no additional computational power in this case, at least from a complexity-theory perspective.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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