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: Foundation for a Formal Refutation of the Original Halting Problem?
    ... Rice said determining whether an arbitrary ... >>language of the TM alone. ... > entering a particular state", ...
    (comp.theory)