<p>It's not uncommon for Wikipedia to say dubious things.  Don't trust it as a primary reference.  Beware that hypercomputation is potentially a &quot;crank-adjacent&quot; subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability.  When you find something in Wikipedia you don't understand, my advice is to look at primary sources, such as good textbooks on the subject.</p>
<p>The statement &quot;the output of a random Turing machine is uncomputable&quot; does not look accurate to me.  It's not even clear to me what that would mean.  I'm not sure how computability would be defined for probabilistic machines -- that would need to be specified before such a statement can be assigned any truth value.</p>
<p>No, in computer science &quot;random&quot; does not mean the same thing as &quot;unknown&quot;.  In lay language &quot;random&quot; can mean &quot;arbitrary&quot; or &quot;I don't understand it&quot; or &quot;hard to predict&quot; or &quot;I don't know what's going on here&quot; or &quot;I don't see an obvious pattern&quot;, but in computer science &quot;random&quot; has a  specific technical meaning taken from probability theory.  See, e.g., <a href="https://cs.stackexchange.com/q/13893/755">https://cs.stackexchange.com/q/13893/755</a>, <a href="https://cs.stackexchange.com/q/7729/755">https://cs.stackexchange.com/q/7729/755</a>.</p>

CC BY-SA 4.0
2020-06-30T17:57:46.777Z
By "crank-adjacent" do you mean on a similar level of quantum physics in mainstream media?
Novicegrammer
CC BY-SA 4.0
2020-06-30T19:24:19.603Z
I love the phrase "crank-ajdacent"!
Andrej Bauer
CC BY-SA 4.0
2020-06-30T17:22:36.303Z
2020-06-30T17:28:34.480Z
2020-06-30T17:28:34.480Z
D.W.
<p>Wikipedia article mentioned : <a href="https://en.wikipedia.org/wiki/Hypercomputation" rel="nofollow noreferrer">Hypercomputation</a></p>
<p>The third paragraph starts off with:</p>
<blockquote>
<p>Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of deterministic, rather than <strong>random</strong>, <strong>uncomputable</strong> functions.</p>
</blockquote>
<p>Furthermore, according to another article, <a href="https://en.wikipedia.org/wiki/Random_Turing_machine" rel="nofollow noreferrer">Random Turing Machine</a>:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>Am I then correct to say, that in this context, the word <strong>random</strong> actually means <strong>unknown secondary input</strong>?</p>
<p>Because from my understanding:</p>
<ul>
<li><strong>Probability</strong> is a well defined area of mathematics</li>
<li><strong>Randomness</strong> is rather a layman's term for &quot;I don't really know what's going on here&quot; or rather &quot;I can't know what's going on here&quot;.</li>
</ul>
<p>Sort of like seeds in PRNGs, an argument can be made that PRNGs are not random at all, after all, the very word <em>pseudo-random</em> is an oxymoron. Given an input and the &quot;hidden input&quot; (seed) I can get the same input back every time.</p>
<p>So in this context, is the output of a RTM <em><strong>reaaaallly</strong></em> uncomputable?</p>

CC BY-SA 4.0
2020-06-30T19:21:44.737Z
Wikipedia is chockfull of half-truths and incorrect statements about mathematics and computer science. They don't let experts fix it without following a myrad of policies, each of which has an acronym.
Andrej Bauer
<computability><turing-machines><randomness>
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
Novicegrammer
# How come Wikipedia says that Random Turing Machines can provide uncomputable output?

(Asked by: username_0 on 2020-06-30)

Wikipedia article mentioned : [Hypercomputation](https://en.wikipedia.org/wiki/Hypercomputation)

The third paragraph starts off with:

> Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of deterministic, rather than **random**, **uncomputable** functions.

Furthermore, according to another article, [Random Turing Machine](https://en.wikipedia.org/wiki/Random_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.

Am I then correct to say, that in this context, the word **random** actually means **unknown secondary input**?

Because from my understanding:

* **Probability** is a well defined area of mathematics
* **Randomness** is rather a layman's term for "I don't really know what's going on here" or rather "I can't know what's going on here".

Sort of like seeds in PRNGs, an argument can be made that PRNGs are not random at all, after all, the very word *pseudo-random* is an oxymoron. Given an input and the "hidden input" (seed) I can get the same input back every time.

So in this context, is the output of a RTM ***reaaaallly*** uncomputable?

**Tags:** computability, turing-machines, randomness
> **Comments:**
> **username_1**: Wikipedia is chockfull of half-truths and incorrect statements about mathematics and computer science. They don't let experts fix it without following a myrad of policies, each of which has an acronym.  

---

## 1 answers

### Answer by username_2 on 2020-06-30. Score: 7 | Accepted answer

It's not uncommon for Wikipedia to say dubious things. Don't trust it as a primary reference. Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability. When you find something in Wikipedia you don't understand, my advice is to look at primary sources, such as good textbooks on the subject.

The statement "the output of a random Turing machine is uncomputable" does not look accurate to me. It's not even clear to me what that would mean. I'm not sure how computability would be defined for probabilistic machines -- that would need to be specified before such a statement can be assigned any truth value.

No, in computer science "random" does not mean the same thing as "unknown". In lay language "random" can mean "arbitrary" or "I don't understand it" or "hard to predict" or "I don't know what's going on here" or "I don't see an obvious pattern", but in computer science "random" has a specific technical meaning taken from probability theory. See, e.g., <https://cs.stackexchange.com/q/13893/755>, <https://cs.stackexchange.com/q/7729/755>.

> **Comments:**
> **username_0**: By "crank-adjacent" do you mean on a similar level of quantum physics in mainstream media?  
> **username_1**: I love the phrase "crank-ajdacent"!  

---

