I was reading something which said:
Less conventional is the Rapidly Accelerating Computer (RAC) whose clock accelerates exponentially fast, with pulses at (say) times $1-2^{-n}$ as n tends to infinity. RAC can cram an infinite number of computations into a single second.It is indifferent to the algorithmic complexity of the task set to it: everything runs, not in exponential or polynomial time, but in bounded time.It can therefore solve the halting problem for Turing machines (which Turing proved algorithmically undecidable) by running a computation in accelerating time and throwing a particular switch if and only if the Turing machine halts. Like all computations carried out by RAC, the entire procedure is completed within one second: it is then sufficient to inspect the switch to see whether it has been thrown.
I think I understand what it's saying. But I also feel that the normal diagonalization argument could show that RACs cannot decide the halting problem.
Can someone help clear up my confusion?
EDIT: Based on the comments, I think I might be misunderstanding the halting problem at a fundamental level. So here is my impression; hopefully someone can point out the error:
Theorem (*): Let $S$ be the set of all binary strings of countably infinite length. Then there is no bijection between the natural numbers and $S$.
This is proven by diagonalization; by letting $HALT=0$ and $NOT\ HALT=1$ etc. we get the application of this theorem to Turing Machines.
The possibilities seem to be:
- (*) is false
- RACs don't provide a bijection
Assuming the truth of (*), why don't RACs show a bijection? RACs can iterate through all TMs, thus building a "bijection table."