<p>Suppose that <span class="math-container">$D$</span> always yields the same value, with probability 1: namely, the value of <a href="https://en.wikipedia.org/wiki/Chaitin%27s_constant" rel="nofollow noreferrer">Chaitin's constant</a>.  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 <a href="https://en.wikipedia.org/wiki/Hypercomputation#Models" rel="nofollow noreferrer">here</a>).  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.</p>
<p>Suppose that sampling from <span class="math-container">$D$</span> 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.</p>

CC BY-SA 4.0
2023-04-06T08:01:52.427Z
2023-04-06T08:01:52.427Z
D.W.
<p>A probabilistic Turing machine uses independent choices, as said in <a href="https://en.wikipedia.org/wiki/Probabilistic_Turing_machine" rel="nofollow noreferrer">Wikipedia</a>.</p>
<blockquote>
<p>At each step, the Turing machine probabilistically applies either the transition function <span class="math-container">$\delta_1$</span> or the transition function <span class="math-container">$\delta_2$</span>. This choice is made independently of all prior choices.</p>
</blockquote>
<p>I am wondering what will happen if we break the requirement of independence.</p>
<hr />
<p>Maybe it is clearer to reformulate it as a Turing machine with an added random tape.
We may define a <em>possibly correlated</em> probabilistic Turing machine as an 8-tuple <span class="math-container">$M = (Q, \Sigma, \Gamma, q_0, A, \delta_0, \delta_1, D)$</span>, where the first seven entries are as standard and <span class="math-container">$D$</span> is a distribution of bit tapes.
Before the runtime, the machine samples a bit-tape <span class="math-container">$r$</span> from <span class="math-container">$D$</span>. And at the <span class="math-container">$i$</span>-th step, the machine uses <span class="math-container">$r_i$</span>, the <span class="math-container">$i$</span>-th bit of the sampled tape to choose which transition function to use, i.e., the machine uses <span class="math-container">$\delta_{r_i}$</span> for the <span class="math-container">$i$</span>-th step.</p>
<p>Let <span class="math-container">$D$</span> be the uniform distribution of bit-tapes where each bit is independently uniform. It is a standard probabilistic Turing machine.</p>
<p>I think this more general notion, possibly correlated probabilistic Turing machine, may bring more computational power.
Is there any paper or discussion about this?</p>

CC BY-SA 4.0
2023-04-06T06:04:15.527Z
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.
D.W.
CC BY-SA 4.0
2023-04-06T06:17:08.463Z
@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.
namasikanam
CC BY-SA 4.0
2023-04-06T06:19:51.450Z
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.
D.W.
CC BY-SA 4.0
2023-04-06T07:46:42.680Z
@D.W. I edited and tried to formalize my question. Do you think it is clear enough?
namasikanam
<turing-machines><probabilistic-computation>
Probabilistic Turing machine of possibly correlated choices
namasikanam
# Probabilistic Turing machine of possibly correlated choices

(Asked by: username_0 on 2023-04-05)

A probabilistic Turing machine uses independent choices, as said in [Wikipedia](https://en.wikipedia.org/wiki/Probabilistic_Turing_machine).

> 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?

**Tags:** turing-machines, probabilistic-computation

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_1**: 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.  
> **username_0**: @username_1 I edited and tried to formalize my question. Do you think it is clear enough?  

---

## 1 answers

### Answer by username_1 on 2023-04-06. Score: 2 | Accepted answer

Suppose that $D$ always yields the same value, with probability 1: namely, the value of [Chaitin's constant](https://en.wikipedia.org/wiki/Chaitin%27s_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](https://en.wikipedia.org/wiki/Hypercomputation#Models)). 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.


---

