Re: Rado's Sigma and the Halting Problem for Programs
From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 08/19/04
- Next message: Mitch Harris: "Re: Proving a negative is hard"
- Previous message: Proprclr: "Re: Dungeon! A Dungeon! (Was: Re: Troll 1, Usenet 0)"
- In reply to: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: Peter R. Douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Reply: Peter R. Douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 19 Aug 2004 04:15:15 GMT
"r.e.s." <r.s@ZZmindspring.com> wrote ...
> "peter_douglass" <baisly@gis.net> wrote ...
> > I think it is a bit tedious to prove with state transition tables,
> > but I think it is straightforward to prove that M' can be
> > constructed for any TM. That's why I gave it as an assumption
> > rather than a lemma. ;-)
>
> FWIW, here's the least tedious way I know of, assuming that
> (1) there is only one halting state,
> (2) 'no' and 'yes' are in the tape alphabet,
> (3) 'no' is only written (if ever) just before halting,
> (4) the transition function is in, say, 5-tuple form.
> Then M' can be constructed from M by replacing each 5-tuple
> of type
> <q s 'no' d Halt>
> with one of type
> <q s 'yes' d Halt>,
> and replacing each 5-tuple of type
> <q s s* d Halt>, where s* is not 'no',
> with n+1 5-tuples of type
> <q s s* d q* >
> <q* s1 s* d q* >
> ...
> <q* sn s* d q* >
> where {s1,...,sn} is the tape alphabet.
>
> Or something very like that, for other varieties of TM.
Hmmm ... I have to retract that, as the situation seems to
be considerably more complicated. That method incorrectly
treats <x,x> as though it were x; that is, instead of
modifying M to M' such that for all x,
Eval(M',x) = 1 if Eval(M,<x,x>) == 0
= _|_ otherwise,
it incorrectly makes M' such that for all x,
Eval(M',x) = 1 if Eval(M,x) == 0
= _|_ otherwise.
It would have been nice to get a proof working entirely
within the TM model, but apparently you're right about it
being too tedious -- if indeed it can be done that way.
--r.e.s.
- Next message: Mitch Harris: "Re: Proving a negative is hard"
- Previous message: Proprclr: "Re: Dungeon! A Dungeon! (Was: Re: Troll 1, Usenet 0)"
- In reply to: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: Peter R. Douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Reply: Peter R. Douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
