Friday, December 16, 2016

[dbcpqerb] Cantor hypercomputer hierarchy

A hypercomputation does an infinite amount of computation in finite time; perhaps each clock cycle is half the length of the previous one, in the style of Zeno's paradox.  (Such a computer cannot realistically be built.)  This can, say, test a property over all integers or all rational numbers.  Supertask.

More powerful would be to test over all real numbers.  More powerful would be to test over all functions over real numbers.  And so on up the Cantor hierarchy of infinities: aleph or beth numbers.

Which computer can calculate the halting probability of a random Turing machine?  I think "all possible Turing machines" is a countable set, and of course the number of cycles a Turing machine runs is also countable.

When a powerful computer capable of testing over all reals or functions runs, what does its output look like?  Find me a noncomputable real number, we tell it.  OK, here is one, it responds, but what does this output look like?  Perhaps the text string "the halting probability of a random Turing machine".

No comments :