8
$\begingroup$

I understand that this thread may be similar to one of my old threads but it's not the same since now I will providing my insight about what I understand.

I understand what the halting problem says, but I can't understand why it can't be solved. My professor used a diagonalization argument that I am about to explain.

The cardinality of the set of turing machines is countable, so any turing machine can be represented as a string. He laid out on the board a graph with two axes. One for the turing machines and one for their inputs which are strings that describe a turing machine and their according input and then he started to fill out the grid with Accept or reject or loop for ever. He then drew out a diagonal along that grid and created a new turing machine with the values in the diagonal. I understand that we are trying to prove that the given language is undecidable. Why is this turing machine that is not in the initial graph important? and how does this lead to the conclusion that the halting problem can't be solved?. I understand why the real numbers are uncountable, so there is no need for explaining that.

I need to understand the proof of why the halting problem can't be solved with the diagonalization argument.

$\endgroup$

closed as off-topic by Andrés E. Caicedo, user91500, Claude Leibovici, Namaste, user21820 Mar 25 '17 at 12:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, user91500, Claude Leibovici, Namaste, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I think this video by the channel Computerphile provides a good explanation of why the Halting problem can't be solved. $\endgroup$ – Tyberius Mar 23 '17 at 3:58
  • 2
    $\begingroup$ This video explains why the halting problem cannot be solved.. $\endgroup$ – Henricus V. Mar 23 '17 at 4:10
  • $\begingroup$ FYI: an intuitive (non-mathematical) explanation provided by many computer science sources: suppose the halting problem is decidable. Then, there can exist a program which checks whether it halts, and in this case, performs some action which prevents it from halting (trivially, a jump/goto to before this check is performed). $\endgroup$ – Jules Mar 23 '17 at 14:27
9
$\begingroup$

Reese did a very good job of explaining how a proof of the undecidability of the halting problem may be written in a way that explicitly makes use of diagonalization. I'll offer an informal gloss.

Diagonalization is employed to reach a contradiction that forces us to abandon an assumption. Here the assumption is the existence of a TM (let's call it $H$) that decides the halting problem.

Diagonalization is applied by building a table $A$ such that that $A_{i,j}$ says whether the $i$-th TM halts on input $j$. We then say, "Let's build a TM that on input $i$ does the opposite of TM $i$."

Now the question is, "Does such a Turing machine exist?" It's not hard to see that given $H$, one can build the desired TM; but then this TM is not in the table, because it was built by diagonalization and yet the table lists all TMs (TMs can be enumerated) ... Contradiction!

The only assumption we can give up is the existence of the TM $H$ that decides the halting problem, which is what we do, so that we are not forced to admit that there is a TM that disagrees with TM $i$ on input $i$ for all $i$.

How would we build the "diagonal TM" given $H$? Just as explained in the "other" proof: duplicate the input, let $H$ decide whether the input TM halts when it reads itself, and then do the opposite of what $H$ said. This last step is diagonalization.

$\endgroup$
  • $\begingroup$ "Now the question is, "Does such a Turing machine exist?" It's not hard to see that given HH, one can build the desired TM". I was watching a video from a UC DAVIS professor, and he came up with that same conclusion. Can you further explain why such Turing machine exists?. The idea is pretty easy to understand. Just flip the values along the diagonal and that will be the result of the new turing machine given input i, but why does it exist? $\endgroup$ – daniel Mar 23 '17 at 5:57
  • $\begingroup$ In the last paragraph of my answer, I mention why the "diagonal" TM would exist. In essence, if you have a subroutine like $H$, the rest is standard stuff: we know how to duplicate an input, and how to implement the negation. $\endgroup$ – Fabio Somenzi Mar 23 '17 at 6:16
  • 1
    $\begingroup$ Perhaps this helps: When we apply diagonalization to prove the uncountability of the reals in $[0,1]$ the result of the construction is clearly an element that we missed inthe purported enumeration. Here we already independetly know that TMs are countable. Hence any TM must appear somewhere in our list. On the other hand, there is no guarantee that there exists a TM that does what we want, unless we assume the existence of $H$. $\endgroup$ – Fabio Somenzi Mar 23 '17 at 6:36
9
$\begingroup$

It doesn't have to do with the uncountability of the real numbers, though the argument is similar.

Based on your most recent edit in response to the comments, it sounds like you don't want the traditional proof, you want the proof your professor was providing. What your professor was doing is in no way standard, so we can only guess; but here's what I think the argument was.

The Turing machines aren't just countable, they can be listed by a Turing machine. So we have an algorithm that lets us list the Turing machines, in order. Suppose we had an algorithm, $H$, that would tell us whether a given Turing machine would halt on a given input. We now construct a new algorithm, $T$, as follows: to determine $T(n)$, we look at the $n$th Turing machine, and ask $H$ whether it halts on input $n$. If it doesn't, we say $T(n) = 0$. If it does, we run that $n$th Turing machine on input $n$, and eventually get a result; let $T(n)$ be that result plus one.

Now, $T$ is an algorithm, so it's represented by a Turing machine. But all the Turing machines were on our list, so $T$ is on our list. Say it's the $N$th Turing machine on our list. What's $T(N)$? If $T$ doesn't halt on input $N$, then at the $N$th step of our construction we decided that $T(N) = 0$, so $T$ does halt on input $N$, a contradiction. If $T(N) = k$ for some $k$, then we decided that $T(N) = k + 1$, another contradiction. But those were the only options - either $T(N)$ doesn't halt, or it eventually outputs some $k$. So this contradicts the supposition that $T$ is actually a Turing machine, which means that the key element - the halting algorithm $H$ - must not exist.

$\endgroup$
  • $\begingroup$ This argument, with relatively minor differences, is in David Harel's Algorithmics. I'm pretty confident the OP's professor presented a proof very close to what you explained. Harel even has a figure that might be very similar to the one alluded to by OP. $\endgroup$ – Fabio Somenzi Mar 23 '17 at 4:44
  • 1
    $\begingroup$ To emphasize: the cardinality is a red herring, merely a distraction. The cardinality follows from the fact that the Turing machines can be listed, and what the proof really needs is the stronger fact: the Turing machines can be listed by a Turing machine, as said in this answer. $\endgroup$ – Colin McLarty Mar 23 '17 at 13:53
  • 1
    $\begingroup$ Why the extra bit about actually running the nth turing machine and outputting a different answer? Wouldn't it be simpler to say "if the n'th turing machine doesn't halt on input n, halt (and, say, output 0); otherwise loop forever"? The thing you're constructing only needs to be a Turing machine; it need not halt on every input. $\endgroup$ – Don Hatch Mar 23 '17 at 17:19
  • $\begingroup$ @DonHatch Sure, but I'm going for clarity rather than pure correctness. To me, it seems clearer to say "these two are different because they give different results" rather than "these two are different because one doesn't give a result and the other does". $\endgroup$ – Reese Mar 23 '17 at 18:15
3
$\begingroup$

Personally, when I learned the halting problem, I like to think of the machine leading to contradiction as the following concrete C program:

#include <stdio.h>
#include <stdbool.h>

/* If we assume the existence of a halting machine 'does_it_halt'.  */
bool
does_it_halt(void *turing_machine, void *input);

/* Then we can build the following machine 'absurd'.  */
void
absurd(void *input)
{
  if (does_it_halt(input, input))
    {
      while (true) {/* infinite loop  */}
    }
  else
    {
      return;
    }
}

/* Now if we run the machine 'absurd' with itself as input, does it halt?  */
int
main(void)
{
  absurd(absurd);
  return 0;
}
$\endgroup$
  • $\begingroup$ That's another way to do it which doesn't make use of diagonalization. $\endgroup$ – DepressedDaniel Mar 23 '17 at 19:13
  • $\begingroup$ @DepressedDaniel: Writing does_it_halt(input,input) is pretty clearly diagonalization. It directly evokes the diagonal of the set $\mathtt{PossibleInputs}\times\mathtt{PossibleInputs}$. $\endgroup$ – Henning Makholm Mar 23 '17 at 19:59
1
$\begingroup$

How do diagonalization proofs work?

Why is this turing machine, that is not in the initial graph, important?

  1. Propose a statement like "there exists a TM that solves the halting problem" or "the reals between 0 and 1 are countable", which we are going to disprove.
  2. Construct a way to enumerate (count off) all the items that are part of the thesis (here: Turing Machines or reals). The items (TMs, reals, ...) must themselves consist of sub-items (e.g., symbols for TMs, digits for reals) so we can make a proper table. It matters not that the table has infinitely many columns and rows. Make this construction as easy/trivial as possible, for bonus points. Easy enough for TMs and reals.
  3. Find a path through your enumeration that hits every single cell. This is where the diagonalization comes in; it makes sure that, unlike following one of the axes to infinity, every cell is reached in a finite amount of steps.
  4. Construct a new item from this walkthrough that is guaranteed not to be a part of the original table. For reals, just add 1 to each digit you encounter (wrapping over). For TMs, do whatever your prof did. As we constructed the table so that it contained all items, we have a contradiction, as this new item is obviously not contained in the table (it is different from every item we encountered / it is new).

Step 4 is the answer to your question:

All our effort was done solely to construct a Turing Machine that is not a member of the set of all Turing Machines. This gives us a contradiction. We carefully constructed our little algorithm so that every step is dead simple and obviously (or, if you so wish, provably) correct, so the only part of our whole diagonalization argument that is negotiable is the conjecture. Hence the conjecture must be false.

Addendum, how to apply for Turing Machines

To apply the diagonalization method for Turing Machines and the halting problem:

  • As hinted to above, we suppose that there is a turing machine H(h,i) that takes two parameters (another TM and some arbitrary input) and decides whether that other TM will halt for said input, or not. This is the definition of the the halting problem.
  • Note that the set of possible inputs (the domain of i) is, again, the set of all turing machines (codified in some textual representation)! This is small enough. This is a similar approach as to say that for reals, it is enough to look at the intervall [0;1] instead of all numbers, for making the proof simpler. We show that the halting problem can not even be solved for this subset of possible machines; i.e., machines that work on the "source code" of machines.
  • The mentioned table lists the machines on one axis, and inputs on the other. Each cell (think of Excel) is the result of running our supposed machine on that specific input. Steps 2 and 3 are thus mechanically performed and need no knowledge whatsoever about Turing Machines.
  • In step 4, we construct a new turing machine H' by going diagonally through the table and making that new machine H' so that it halts if the cell contains FALSE, and does not halt if the cell contains TRUE. This is very easy to do since H' can contain H as a subroutine and ask that one, then either exit or enter an infinite loop (which is easy to program).
  • As with the reals, we have now created a new entry for our table which by mere definition differs from every other entry. q.e.d.
$\endgroup$
  • $\begingroup$ the namegiver of this proof is simply the way to walk through everything, even if it takes infinitely many steps This kind of misses the key idea that reaching any particular element should only take a finite number of steps. This is why you can't do "linearization" where you do the whole first row first, then the second, row, etc. $\endgroup$ – DepressedDaniel Mar 23 '17 at 19:32
  • $\begingroup$ Thanks, @DepressedDaniel, I have modified my sentence accordingly. $\endgroup$ – AnoE Mar 23 '17 at 19:39

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