Wikipedia article mentioned : 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:

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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jun 30 '20 at 19:21

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.

  • $\begingroup$ By "crank-adjacent" do you mean on a similar level of quantum physics in mainstream media? $\endgroup$ – Novicegrammer Jun 30 '20 at 17:57
  • 2
    $\begingroup$ I love the phrase "crank-ajdacent"! $\endgroup$ – Andrej Bauer Jun 30 '20 at 19:24

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.