Re: Foundation for a Formal Refutation of the Original Halting Problem?

From: Michael N. Christoff (mchristoff_at_sympatico.caREMOVETHIS)
Date: 08/04/04 

Date: Wed, 4 Aug 2004 12:01:50 -0400

"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message
news:2ncdavFs8okeU1@uni-berlin.de...
> Michael N. Christoff <mchristoff@sympatico.caREMOVETHIS> wrote:
> >"Martin Shobe" <mshobe@sbcglobal.net> wrote in message
> >
> >> From what I understand, Rice's theorem rules this out. Essentially,
> >> the set of TM's that "contain" a Halt program isn't Turing computable.
> >>
> >
> >I'm not so sure about that. Rice said determining whether an arbitrary
TM
> >has a particular property is impossible if: the property holds for some
but
> >not all TMs, and the property depends on the TM's output (language)
alone -
> >not its construction*.
>
> Right. so it -is- possible to do things like count the number of states
> (er.. decide if the number of states is a certain number).
>
> >The property P = "does not contain a Halt program"
> >is a property of the specific construction of the TM. For example, we
can
> >have two TM's M,N that decide the same language but where M contains a
Halt
> >function and N doesn't (ie: M could use the halt function only on N
which
> >would always return true). Hence the property cannot be discerned from
the
> >language of the TM alone.
>
> I disagree based on what I consider "contain" to mean. If it means "there
> is a subset of states and transitions, such that halting is determined by
> entering a particular state", I'd have to say no.
> That is a property of
> the language, not the structure alone.
>

Let P = "contains a subset of states and transitions, such that ~the Halt
program's output~ is determined by entering a particular state".
(I've changed your quote to what I assume you meant, please correct me if
I'm wrong). Are you saying that you cannot have two TMs that recognize the
same language where one has property P and the other does not?

l8r, Mike N. Christoff

Relevant Pages

  • Re: Flight only among Insecta?
    ... technical subjects the precise meanings of words is important. ... language is not carefully used. ... which would be utterly inappropriate in a technical or legal context. ... If you are alone, and, alas! ...
    (talk.origins)
  • Re: Flight only among Insecta?
    ... language is not carefully used. ... rising moon, which just sufficed to give a sheen to the water beneath ... would sleep, it is of all lullabies the sweetest. ... If you are alone, and, alas! ...
    (talk.origins)
  • Re: Flight only among Insecta?
    ... technical subjects the precise meanings of words is important. ... language is not carefully used. ... which would be utterly inappropriate in a technical or legal context. ... If you are alone, and, alas! ...
    (talk.origins)
  • Re: Armenia, homeland of the Etruscans?
    ... data, let alone the Etr. ... The book Five Texts in Etruscan, ... Language of Tyrrhenians and Ancient Jutes, ... I don't know what "weaving one's home place of coves" might be ...
    (sci.lang)
  • Re: Armenia, homeland of the Etruscans?
    ... data, let alone the Etr. ... gives first the English translation, then the Etruscan words, ... The book Five Texts in Etruscan, ... Language of Tyrrhenians and Ancient Jutes, ...
    (sci.lang)