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

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

Date: Thu, 12 Aug 2004 02:35:39 GMT

"peter_douglass" <baisly@gis.net> wrote ...
-snip-
> I believe the Halting Theorem may be proven without recourse
> to reductio ad absurdum. Here is my stab at it.
-snip-

> Assume that from a Turing Machine M we can construct
  ^^^^^^
> a Turing Machine M' such that the following holds:
> Eval(M',x) == begin
> if Eval(M, <G'(M'),x>) == "no"
> then return "yes"
> else loop_forever() ;
> end
-snip-

Can you prove, without reductio ad absurdum, that such
an M' can always be constructed?

The self-referring definition of M' would seem to make
that less tractable than the usual type of definition of
a "derived TM" for reductio ad absurdum, e.g. (using the
usual shorthand suppressing the encoding of TMs & inputs):
  M'(P) converges iff M(P,P) converges to "no".
Defining M' in terms of M alone is tractable, but your
version may not be. (?)

--r.e.s.

Relevant Pages