7
$\begingroup$

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:

  1. (*) is false
  2. 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."

  • 1
    @Vladimir: https://en.wikipedia.org/wiki/Thomson%27s_lamp2015-07-28

2 Answers 2

6

It feels like you're conflating the uncountability of the reals with the undecidability of the halting problem - while the diagonalization arguments are related, that doesn't mean that there's 'no bijection between programs and halting states' as you say in your comment on the question.

The best way of thinking of the 'halting problem' might be this: firstly, the set of Turing Machines is countable, and so we can put it into one-to-one correspondence with the integers (can you see why?). Since the input to a given TM can also be represented as an integer and since there's a one-to-one correspondence from pairs of integers to integers, we can rephrase the question 'does the Turing Machine with index $x$ halt on input $y$?' as the question 'is the integer $\left$ in the halting set $H$?'. (Can you see why this is equivalent to the question 'does the Turing Machine with index $z$ halt on empty input?')

The diagonalization argument then shows that no TM can compute the set $H$ - but that doesn't imply that the set $H$ doesn't exist. It's a perfectly valid mathematical object, and we can study it; what's more, we can imagine that we know the set $H$ (in other words, that we have an oracle that takes an integer as input and tells us whether that integer is in $H$ or not) and ask what problems are solvable with knowledge of $H$, and moreover whether there are any problems that aren't solvable even knowing $H$. But now, as several people have suggested, the same style of diagonalization argument works over 'machines that know the set $H$' to provide a new set $L$ of machine indices such that even machines with knowledge of $H$ can't compute whether a given integer is in the set $L$ or not. Going on, we can in fact (as sdvcc suggests in comments) construct an infinite series of sets of integers such that even a machine with an oracle for the previous set in this series can't determine membership in the next set. These are usually labelled as 0', 0'', \ldots, 0^{(n)}, where $0^{(n+1)}$ is (essentially) the 'halting set' of indices of machines with knowledge of $0^{(n)}$. But note that each set $0^{(i)}$ is just another set of integers.

In fact, there are even sets of integers - we'll call one $I$ - such that a regular Turing Machine can't compute the set $I$ (i.e., can't answer questions 'is the number $x$ in $I$?), but a Turing Machine with the set $I$ still can't answer questions about the halting problem $H$; $I$ is said to be an intermediate set, and the existence of these sets wasn't proved for several decades after the concept of the TM was discovered. If you're interested in more details on these sorts of questions of what Turing Machines can and can't compute, the magic words to search for are Recursion Theory - there's quite a bit more to the topic than I could even begin to hint at here.

  • 0
    Likewise, the version of it for TMs doesn't say that the halting set doesn't exist - or more particularly, it doesn't say that there's an 'ur-halting set' that no oracle TM can compute - it just says that, for any given list of TMs there's some set that those TMs can't compute the membership problem for. But 'these TMs can't compute the set X' is different than 'the set$X$doesn't exist'. It just makes it difficult to talk about the set X!2012-01-26
3

Diagonalization can only be used for showing a machine of type $X$ can't solve the halting problem for machines of type $X$.

This machine isn't a turing machine, (it's not even a computer according to conventional usage), so it's consistent that it solves the halting problem for turing machines, but it can't solve the halting problem for RAC's.

For your edit:
There are only a countably infinite number of turing machines. Just as there are countably many natural numbers. But there are uncountable many infinite binary strings, just as there are uncountable many real numbers.

  • 0
    While an RAC can compute the halting problem for Turing machines (so there are elements of N which map via RACs to the halting set), no RAC can compute the "halting problem" for RACs [say, the set of RAC computations which end in the first bit of the tape being a 1]. This problem, then, is an element of $S$ which is not in the range of the RAC computation function.2014-12-08