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

From: Mike N. Christoff (dmx_dawg_at_hotmail.com)
Date: 08/10/04 

Date: 9 Aug 2004 21:19:41 -0700

"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote in message news:<NomQc.29182$Jq2.1364630@news20.bellglobal.com>...
> "Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message
> >
> > I think Rice's theorem states that it is undecideable
> > whether the -language- a given TM recognizes has a
> > particular non-trivial property.
> >
>
> Exactly. So Rice's result does not apply to this particular property, since
> we can have two distinct TMs with the same language that at the same time do
> not share the property P. ie: the property P is language independent.
>

I've been away for a while, but I thought I'd clarify this point.
Instead of possibly confusing the issue further (ie: are we talking
about properties of TMs or of the language of the TM?) I thought it
best to simply post the theorem itself verbatim:

Rice's Theorem
Let P be any problem* about Turing machines that satisfies the
following two properties:

a) For any TMs M1 and M2, where L(M1) = L(M2), we have <M1> in P iff
<M2> in P. In other words, the membership of a TM M in P depends only
on the language of M.

b) There exist TMs M1 and M2, where <M1> is in P and <M2> is not in P.
 In other words, P is nontrivial - it holds for some TMs, but not all.

If P satisfies the conditions above, then P is undecidable.

-----

Notation:
If M is a TM, then <M> is a specific encoding of M as a binary string.

L(M) = the language of the TM M.

* -
By "P is a problem about Turing machines", it is meant that P is a
subset of the set of all Turing Machine encodings (which means it is a
formal language over the set of TM encodings). Hence notation like
'<M> in P' (where 'in' implies set membership) is equivalent to saying
'M has property P' as was done in earlier posts. So:

P = {<M> | M is a TM that contains a Halt function}

l8r, Mike N. Christoff

Relevant Pages

  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... > not share the property P. ie: the property P is language independent. ... about properties of TMs or of the language of the TM?) ... Let P be any problem* about Turing machines that satisfies the ... formal language over the set of TM encodings). ...
    (comp.theory)
  • Re: Quieter glyphs than parentheses
    ... ASCII or 16-bit Unicode characters, it did not require rewriting the entire ... by non ISO8859 language scripts. ... Japanese has three popular non-Unicode-based encodings, ... display fonts is one reason I would caution against using characters from ...
    (comp.lang.lisp)
  • Re: Creating functions for Kabbalah
    ... >> that produce meaninfull relationships within the language.. ... Let me explain what we are doing in common english for you, ... These encodings use what is called Concentation. ... Some might say the only universal truth in language is simply the ...
    (sci.math)
  • Re: Turing Machines and Physical Computation
    ... For those who claim that Turing machines must be physical, ... outputs yes when given a string in the language, ... If all you have are regular languages, ... then all you need are finite state machines. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... For those who claim that Turing machines must be physical, ... outputs yes when given a string in the language, ... If all you have are regular languages, ... then all you need are finite state machines. ...
    (sci.math)
Quantcast