Help with undecidable problem

From: Francesco Gallarotti (gallarotti_at_hotmail.com)
Date: 12/15/03 

Date: Mon, 15 Dec 2003 16:02:09 GMT

I would really appreciate if anybody could explain me AS IF I WERE 4 YEARS
OLD, how to proof that:

"Given a Turing Machine M, does M halt on the empty tape?" is an undecidable
problem

starting from the Halting problem:

"Given a Turing Machine M and an input string "w", does M halt on "w"?"

I would enjoy a simple explanation step by step from somebody who has a good
grasp on this material.

This is not a homework. In fact this is in preparation for a final exam.
thanks...

FG

Relevant Pages

  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (comp.theory)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (sci.logic)