Re: Rado's Sigma and the Halting Problem for Programs

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 08/14/04 

Date: Sat, 14 Aug 2004 01:10:55 GMT

"peter_douglass" <baisly@gis.net> wrote ...
> "r.e.s." <r.s@ZZmindspring.com> wrote in ...
> > Can you prove, without reductio ad absurdum, that such
> > an M' can always be constructed?
>
> Hmm. I'm not sure. I think you have pointed out a bug
> in the proof. Better would be
>
> Eval(M',x) == begin
> if Eval(M,<x,x>) == "no"
> then return "yes"
> else loop_forever() ;
> end

That works. (BTW, in the proof, I think you mean
to say "computes" everywhere you wrote "implements".)

> Hope there is nothing so wrong with
> the "corrected" version.

For certain classes of TM, the missing step of proving that
TM M' can always be constructed, is straighforward I think.

--r.e.s.

Relevant Pages