Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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."

share|improve this question
2  
The informal argument is absolutely convincing. I want one. –  André Nicolas Jan 26 '12 at 15:40
2  
In order to figure out how (or if) the diagonalization argument would fail, you'd need a more formal description of exactly how the machine works and what its state is after the infinitely many steps would be. (How does it look afterward if the machine flips the switch back and forth infinitely many times?). One interesting proposal is described in the top answer to this recent question. –  Henning Makholm Jan 26 '12 at 15:54
3  
If instead of RAC you have a Turing machine with an oracle for halting problem (call that $TM+O$), then you can solve halting problem for TM, but, as the diagonal argument shows, you cannot solve halting problem for $TM+O$. This is a harder problem. You can go further - a Turing machine with an oracle for halting problem for $TM+O$, call it $TM+O^2$, can solve halting problem for $TM+O$, but not $TM+O^2$. Even more, if $TM+O^{\omega}$ is a Turing machine with oracle for $TM+O^n$ for any finite $n$, then it can solve halting problem for $TM+O^n$ for any finite $n$, but not for $TM+O^{\omega}$. –  sdcvvc Jan 26 '12 at 16:58
    
@sdvvc: Then maybe my questions is: how is a "halting oracle" a well-defined phrase? My understanding is that there simply is no bijection between programs and halting states, so to have a program which finds such a bijection would be like finding a TM that proves $1+1=3$. –  Xodarap Jan 26 '12 at 17:37
2  
Xodorap: Take the set $A=\{(M,w):M \text{ is a Turing machine halts on } w\}$. It is countably infinite. A machine with oracle supplies a pair $(M,w)$ (which is encoded as a finite string, say in binary) and it receives, out of the blue, yes/no answer whether the pair is in $A$. So Turing machines with oracles are well-defined. –  sdcvvc Jan 26 '12 at 20:13

2 Answers 2

up vote 6 down vote accepted

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<x,y\right>$ 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.

share|improve this answer
    
"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." - Thank you, this is the crux. It seems to me that a diagonalization requires nothing about the capabilities of the TM, so I (incorrectly) conclude that it's unsolvable independent of the machine's capabilities. Where am I going wrong? –  Xodarap Jan 26 '12 at 21:15
    
@Xodarap I think you're going wrong in translating backwards: you have an essentially correct argument (with a lot of details that need filling in!) that for any given oracle set $O$, there is a set $O'$ that can't be computed by a TM with access to the set $O$. But that's different from the statement that 'there's some set $X$ that can't be computed by any Turing Machine+oracle combination', because a TM with access to the oracle for $X$ can always compute it! –  Steven Stadnicki Jan 26 '12 at 21:21
    
It's essentially the difference between 'for all $x$, there exists a $y$' and 'there exists a $y$ such that for every $x$'. In fact, your argument can be extended to show that there are infinitely (uncountably!) many degrees, where two sets have the same degree if they're 'Turing-Equivalent' - if a TM with access to an oracle for one can compute the other. –  Steven Stadnicki Jan 26 '12 at 21:25
    
Sorry to be thick, but I still don't understand. For ex, what is wrong with this proof that $O'$ cannot exist: if $O'$ did exist, then we could fill out the a table of $O$. Yet we know by diagonalization we can't create a table $O$. QED.? –  Xodarap Jan 26 '12 at 21:31
    
Xodarap: I think you need to be a lot more specific about what you mean by 'table'. (And for that matter, by diagonalization!) For instance, Cantor's proof doesn't say that there's a real number that doesn't exist - just that, for every means that we can come up with of enumerating the real numbers, there's some number outside our enumeration. –  Steven Stadnicki Jan 26 '12 at 21:33

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.

share|improve this answer
    
Thank you. It sounds like option #2 which I listed in my edit is the correct one. But could you explain why? It seems like the $N\to S$ direction can be found by solving the halting problem, and $S\to N$ by just looping through programs until you find one with the correct halting pattern so... why isn't this a bijection? –  Xodarap Jan 26 '12 at 20:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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