Re: Rado's Sigma and the Halting Problem for Programs
From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 08/14/04
- Next message: Bryan Olson: "Re: What is the Result from Invoking this Halt Function?"
- Previous message: Diglio A. Simoni: "Re: Analysis of Algorithms"
- In reply to: peter_douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Reply: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 14 Aug 2004 07:33:51 GMT
"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.
--r.e.s.
- Next message: Bryan Olson: "Re: What is the Result from Invoking this Halt Function?"
- Previous message: Diglio A. Simoni: "Re: Analysis of Algorithms"
- In reply to: peter_douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Next in thread: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Reply: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
