Re: Yet another Attempt at Disproving the Halting Problem

From: Anonymous (anonymous_at_home.net)
Date: 07/28/04 

Date: Wed, 28 Jul 2004 00:11:02 GMT

Because TMs can ALWAYS be applied to themselves, so the erroneous conclusion
stems from somewhere else ... namely the assumption that the machine existed
in the first place.

"Peter Olcott" <olcott@worldnet.att.net> wrote in message
news:DLBNc.142504$OB3.109241@bgtnsc05-news.ops.worldnet.att.net...
>
> "Rick Decker" <rdecker@hamilton.edu> wrote in message
news:4106C2E8.2000900@hamilton.edu...
> >
> >
> > Peter Olcott wrote:
> >
> > > I'm not doing that one any more. I am sticking to TM's, and
> > > state transition diagrams. I don't want to bother proving anything
> > > unless the proof is in the commonly accepted format, with the
> > > usual amount of rigor and formalism.
> > >
> > <snip>
> >
> >
> > While that seems like a good approach, you run a bit of
> > a risk if you emulate Linz's exposition. The problem is
> > that while his proof is perfectly correct, his use of
> > instantaneous descriptions to describe the configuration
> > of a TM may distract you from the meat of the proof.
> >
> > What the heck, give it a try if you want. I would urge
> > you, though, to first read through his proof with
> > sufficient care that you are absolutely certain about
> > what is being done there. Here's the idea, again:
> >
> > 1. Assume a TM H exists with the following properties:
> > a. H takes as its input a description w_M of a TM
> > M and a word w.
> > b. When given such an input, H always eventually
> > enters one of two final states, q_y or q_n.
> > c. H enters q_y if and only if M would halt when
> > started with input w.
> > d. H works as described above for *all* M and w.
> >
> > 2. Use H to make a new TM H^ (details omitted) and
> > observe that for some inputs, H^ halts if and
> > only if it doesn't halt.
> >
> > 3. Note that H^ behaves in a nonsensical way, so
> > either the assumption in (1) was wrong or
> > the construction in (2) was invalid.
> >
> > 4. Since the construction in (2) is obviously
> > valid, the only possible conclusion is that
> > we were incorrect in assuming (1), i.e., that
> > such a machine H existed. In Linz's words, "[T]he
> > contradiction tells us that our assumption
> > of the existence of H, and hence the assumption
> > of the decidability of the halting problem,
> > must be false."
> >
> > Once the "aha" light goes on, you'll appreciate
> > how lovely the argument really is.
> >
> >
> > Best of luck,
> >
> > Rick
> >
>
> But how is that not simply a proof showing that a TM
> can be screwed up such that when applied to itself, it
> derives an erroneous conclusion?
>
>

Relevant Pages
Loading