Need help proving a variation on the halting problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

JTHM
Posts: 16
Joined: Sun Apr 22, 2012 4:29 am UTC

Need help proving a variation on the halting problem

Postby JTHM » Sun Apr 22, 2012 6:43 am UTC

I'm a philosophy student working on a certain proof involving computability theory, and there's a lemma that I'm trying to prove which, if true, would almost finish the job for me. I hope that one of you better versed in theoretical computer science than I will be able to help me.

Specifically, what I need is a proof of the following statement: Given a non-empty set of tuples, each enumerating a specific Turing machine and some input string, no algorithm can always determine how many of those turing machines will halt for their associated inputs. Moreover, there are an infinite number of such undecidable input sets for every possible cardinality; e.g. among the sets containing one such tuple, an infinite number are undecidable, among the sets containing two such tuples, an infinite number are undecidable, and three, four, etc, all the way on to infinity. Finally, for all natural numbers n, an infinite number of sets of the form described above containing tuples containing n distinct Turing machines (as opposed to just distinct pairings of Turing machines and input strings, which would allow a set containing tuples which all contained the same Turing machine but with different inputs) are inputs for which this problem cannot be decided.

This not the same as the (well-known-to-be-undecidable) halting problem as usually stated, which asks whether, given a single Turing machine and a single input string, "Will the TM halt on this input?" The above problem asks not WHICH of the Turing machines will halt, but rather, HOW MANY. So, for example, given an input of the form {<TURINGMACHINE1,inputstring1>,<TURINGMACHINE2,inputstring2>}, an oracle that could compute this problem might return an answer of the form "One is undecidable, and one is not," without saying which one (which is what an oracle that could solve the halting problem would do).

I would very much appreciate it if, should you know of a proof that the above is true, or know of related proofs that I should look at, you would be so kind as to include citations (or even just the name of the proof, the author, or a book/webpage in which it/they appear) in your reply. I will, after all, need to cite this in my finished paper.

Thank you in advance, denizens of XKCD, and +1000 internets upon whomever cometh to my rescue.

Edit: the title of this thread should have been "Need help proving the undecidability of a variation on the halting problem," not "Need help proving a variation on the halting problem," which makes no sense. I was tired when I posted.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Need help proving a variation on the halting problem

Postby ++$_ » Sun Apr 22, 2012 7:48 pm UTC

I don't know where (or if) this appears in the literature, but unless I'm missing something, I think the proof is straightforward.

Suppose, for purposes of contradiction, that you have an oracle that can solve your problem for a collection of n Turing machines. We will show, by induction, that we can use this oracle to solve the halting problem.

If n = 1, then we can obviously use the oracle to solve the halting problem. Just take the Turing machine of interest and plug it into the oracle. If it says "One of these machines halts," then it halts. If it says "Zero of these machines halt," then it doesn't halt. This is the base case.

Now, for the induction step, assume that we know how to use an oracle that solves the problem for a collection of n-1 Turing machines to solve the halting problem, but all we have is an oracle that can solve the problem for a collection of n Turing machines. In that case, we feed our oracle the collection of n-1 Turing machines of interest, plus an additional Turing machine that is known to halt. (It is not so hard to come up with a Turing machine that halts -- just make its final state equal to its start state.) The number the oracle spits out is exactly 1 more than the number of the original n-1 Turing machines that halt, so by subtracting 1 we get the number we would have gotten from the (n-1)-oracle. Now use that number to solve the halting problem.

Hence we can use this oracle to solve the halting problem, no matter how many Turing machines the oracle requires as input. This is a contradiction.

I believe a similar argument will work for the other two cases, although it might require a little more care (especially in the last case, because there you have to produce a NEW Turing machine that halts). I haven't actually tried it, but I am confident.

JTHM
Posts: 16
Joined: Sun Apr 22, 2012 4:29 am UTC

Re: Need help proving a variation on the halting problem

Postby JTHM » Sun Apr 22, 2012 8:43 pm UTC

Thanks, ++$_. When you explain it that way, it does seem embarrassingly obvious. (You were a BIG help, though.)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests