Re: [isabelle] Formalizing Turing machine



On Wed, 2009-09-30 at 08:49 -0600, Konrad Slind wrote:
> On the face of it, even the undecidability of the Halting
> Problem seems to need sets to state (i.e. the *set* of all
> halting TMs is undecidable).

There is no need to talk about the "set of all halting TMs" to state
undecidability of the halting problem.  Simply put, undecidability of
the halting problem asserts that there is no Turing machine that decides
whether an arbitrary Turing machine halts.  Stating this requires
quantification over all Turing machines, but no set comprehension.  (Of
course, you chose a deliberately careful wording in the first place, so
I guess this was obvious to you.)

Maybe someone else can point out the precise theory required to prove
undecidability of the halting problem?

Regards,
Tjark






This archive was generated by a fusion of Pipermail (Mailman edition) and MHonArc.