3
$\begingroup$

Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.

In this entry it is said:

A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape

Does that mean that, theoretically, generalized Turing machines, cannot compute all reals? Can generalized Turing machines do (fully) hypercomputation (theoretically)?

(I know that there is strong evidence against hypercomputation. I'm asking this only from a theoretical perspective)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine models fail to compute almost all real numbers.

In fact, the alphabet need not be fixed. It is enough that the alphabet is taken from some countable set of finite alphabets, for example $\{1,\ldots,n\}$ for every $n$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ And are generalized Turing machines described by a string over a fixed alphabet? $\endgroup$
    – sztorwi
    Feb 14, 2019 at 10:30
  • $\begingroup$ Even if the alphabet is $\{1,2,\dots,m\}$ for arbitrary $m$, the same proof works. $\endgroup$
    – Yuval Filmus
    Feb 14, 2019 at 10:55
  • $\begingroup$ There is something I do not understand yet. In wikipedia entry about hypercomputation it says "A real computer (a sort of idealized analog computer) can perform hypercomputation if physics admits general real variables (not just computable reals), and these are in some way "harnessable" for useful (rather than random) computation. This might require quite bizarre laws of physics (for example, a measurable physical constant with an oracular value, such as Chaitin's constant), and would require the ability to measure the real-valued physical value to arbitrary precision." @YuvalFilmus $\endgroup$
    – sztorwi
    Feb 14, 2019 at 12:16
  • $\begingroup$ And Schmidhuber's computers seem to use this (specifically, Chaitin's constant): "Jürgen Schmidhuber (2000) constructed a limit-computable "Super Ω" which in a sense is much more random than the original limit-computable Ω, as one cannot significantly compress the Super Ω by any enumerating non-halting algorithm." (Ω being Chaitin's constant). Wouldn't that mean that these computers would use real numbers to perform hypercomputation? Wouldn't that mean that they compute all real numbers? @YuvalFilmus $\endgroup$
    – sztorwi
    Feb 14, 2019 at 12:18
  • 1
    $\begingroup$ No. The proof works as long as the machine model satisfies its premises. There's no way around it. This is the advantage of mathematical proofs. They are 100% correct. $\endgroup$
    – Yuval Filmus
    Feb 14, 2019 at 12:34

Your Answer

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

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