Re: Daryl, Dave, Barb and the Georges' source of Confusion

From: Acid Pooh (poohonlsd_at_yahoo.com)
Date: 07/04/04 

Date: 4 Jul 2004 01:37:56 -0700

"|-|erc" <gotcha@beauty.com> wrote in message news:<WkKFc.77385$sj4.57018@news-server.bigpond.net.au>...
> "Acid Pooh" <poohonlsd@yahoo.com> wrote in
> > "|-|erc" <gotcha@beauty.com> wrote in >
> > <multiple snips>
> > >
> > > "Does a program exist that can systematically tell me whether a given input program will halt?"
> > >
> > >
> > > The correct answer is, COULD BE, as long as it doesn't analyse itself.
> > >
> > > A trillion dollar software industry suggests it could be an interesting problem.
> > >
> >
> > This is a fair enough line of thought, especially since Turing didn't
> > address this issue in his proof. However, the answer is still "No."
> > The short explanation would appeal to Rice's theorem. I'm still
> > trying to formulate the long one (so, this is a "work in progress" --
> > feel free to ask questions) Let f be a computable function. There
> > are infinitely many TMs which compute f. Given a fixed index, the
> > TM's will all have pair-wise distinct Godel numbers.
> >
> > Now, if H and H' both decide if all pairs (M,i) halt (except for (H,H)
> > and (H',H') respectively, in accordance to your condition, we can
> > construct a new TM D (for "D'oh") as follows:
> >
> > function D(s)
> > begin
> > if H'(s, s) = "no"
> > then return("yes")
> > else ... some infinite loop ...
> > end
> >
> > Now, does D(H) halt? (That is, D on Hs' Godel number). If it does,
> > then we know that H'(H,H) = "no". But H' and H compute the same
> > function, so H(H,H) = no. Contradiction. If it D(H) doesn't halt,
> > then H'(H,H) does halt. Contradiction again.
> >
> > This might seem like a toy generalization, but it really has a lot of
> > power. You might think that you can simply exclude all such H's
> > (H-primes) from the domain of H. However, you can't effectively do
> > that. By Rice's theorem, there is no algorithm which can determine if
> > a given TM is an element of the set of all TMs which compute the same
> > function.
> >
> > Does that help?
> >
>
> the parameters considered as referencing halt would include (H, x), (H', x) forall x.

But H' *doesn't* reference H. That's the whole point.

>
> [Herc]
> The (new) objective is to detect if a function refers to Halt.
>
> [Acid]
> If it cannot detect equivalent functions to halt, by Rice Theorem,
> then it must output from the 1st 2 options instead for some references to equivalent functions.
> Whatever of these deterministic flags it outputs, D() will output a contradictory result.
>

I'm not sure if I understand what you think my reply would have been.
;-)

The idea is that H(x,y) = H'(x,y) for each x,y. That is, they both
evaluate the same function. However, they use different algorithms to
do it. So you can effectively substitute an occurrence of H by H' in
a function and still compute the same function. H', however, does not
refer to H. That's like saying that <insert new primality test>
refers to the Sieve of Erasthosanes.

> These 2 assertions could also contradict.
> > Let f be a computable function. There
> > are infinitely many TMs which compute f. Given a fixed index, the
> > TM's will all have pair-wise distinct Godel numbers.
>
> If a function is designed to monitor its own godel number, it may have no equivalent
> function. "Output yes iff your godel number is 777". If that function has godel number
> 777 then there is no equivalent function. Old crippleware technique!

Heh. You want a program to encode its own Godel number. Sheesh,
that's about as self-referential as one can get. Anyways, try looking
up the Fixed-Point theorem. It's used as a lemma in proving Rice's
theorem and it bears on this. (I don't remember enough about it to
actually comment on your idea)

'cid 'ooh

Relevant Pages