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

From: |-|erc (gotcha_at_beauty.com)
Date: 07/04/04 

Date: Sun, 04 Jul 2004 02:55:50 GMT

"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.

[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.

A few weaknesses to the argument. There probably are systematic ways to develop
non self referential code. **

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!

Herc

**
> >>Result: f(x) = x*x
> >>
> >>f(x) is primitive recursive. Which rule do you want to throw out that
> >>will prevent f(x) but still let you do addition?
> >>
> >
> >
> > Way ahead of you Robin!
> >
> >
> >>>4) If g1, g2, .. gm, are primitive recursive and n-ary, and h is
> >>>primitive recursive and m-ary then so is n-ary f defined as
> >>> f(x1,x2,...,xn) = h(g1(x1,x2,...,xn),...,gm(x1,x2,...,xn))
> >
> >
> > Improvement :
> >
> > 4) If g1, g2, .. gm, are primitive recursive and n-ary, and h is
> > primitive recursive and m-ary then so is n-ary f defined as
> > f(x1,x2,...,xn) = h(g1(z1*x1,z2*x2,...,zn*xn),...,gm(zm1*x1,zm2*x2,...,zmn*xn))
> >
> > where
> > z1 or z11 or z21 or ... or zm1 = 1 (exclusively)
> > z2 or z12 or z22 or ... or zm2 = 1
> > ...
> >
> > otherwise zxy = 0
> >
> > That way each parameter of f is only used once.
>
> Ok, this works for +, *, ^, ^2. I'll have to look and see if it causes
> problems with - and /. Also, since squaring is equivalent to self
> multiplication, what have you gained? Wouldn't it be easier to stick to
> primitive-recursive functions as they are and just ignore the halting
> problem completely?
>

Relevant Pages

  • Re: Daryl, Dave, Barb and the Georges source of Confusion
    ... > TM's will all have pair-wise distinct Godel numbers. ... If it Ddoesn't halt, ... Contradiction again. ... If it cannot detect equivalent functions to halt, by Rice Theorem, ...
    (sci.logic)
  • Re: Daryl, Dave, Barb and the Georges source of Confusion
    ... > TM's will all have pair-wise distinct Godel numbers. ... If it Ddoesn't halt, ... Contradiction again. ... If it cannot detect equivalent functions to halt, by Rice Theorem, ...
    (sci.math)
  • Re: model theory: Whats the big picture?
    ... suppose I know someone who is going to teach himself calculus. ... Axiom of Choice all the time. ... that assuming AC is going to lead to a contradiction, ... "Understanding Godel isn't about following his formal proof. ...
    (sci.logic)
  • Re: proof of undecidability of halting problem
    ... however, the contradiction is introduced by using a second function, ... a function like halt can't? ... Turing proved it could be done. ... How can a high level language prove theorems ...
    (sci.logic)
  • Re: Daryl, Dave, Barb and the Georges source of Confusion
    ... >> are infinitely many TMs which compute f. ... > The objective is to detect if a function refers to Halt. ... > If it cannot detect equivalent functions to halt, by Rice Theorem, ...
    (comp.theory)