Re: [PO] Re: Proving a negative is hard

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 08/23/04 

Date: Mon, 23 Aug 2004 08:33:45 +0000 (UTC)

Peter Olcott wrote:
> "Daryl McCullough" <daryl@atc-nycorp.com> wrote in message news:cgauts0147t@drn.newsguy.com...
>
>>Peter Olcott says...
>>
>>>The problem is not that the standard proof does not apply in my
>>>case.
>>
>>Yes, it is. The standard proof is about computable *functions*,
>
> The standard proof arbitrarily restricts itself the mathematical
> functions.

It's about mathematics and mathematical stuff. In case you hadn't
noticed, Alan Turing was a /mathematician/.

> It is possible for software functions to selectively
> refuse the provide a result. It is not possible for mathematical
> function to do this. This is the specific gap between the mathematical
> abstraction, and the actual Turing Machine implementation.

Disproof: the following /mathematical/, partial function, f : N ->
{strings}, exists:-

                { "1" : x = 1;
                {
                { " " : x = 2;
         f(x) = {
                { "" : x = 3;
                {
                { undefined : x > 3.

>>where the output is a deterministic function of the inputs. So
>>H(x,y) *always* halts and *always* returns the same value for
>>the same inputs x and y. You are proposing a program that doesn't
>>have those properties. So the proof doesn't apply. That doesn't
>>mean that an *analogous* proof won't work. I gave you a proof
>>that works for your modified conventions.
>
> I saw no possible way that you could make creating a TM
> that can actually implement the behavior of LoopIfHalts in
> the case where my method is implemented. I did have to
> augment my method to accommodate your excellent objections.
> This slightly revised method sure seems airtight to me.
> Can you find a leak anywhere?

Again, your special 'UTM', V, can /itself/ be part of another TM, D
(perhaps by having an ordinary UTM, U, as part of D, and having U
simulate V). Your alleged halt analyzer, P, runs as a full program (not
part of another program) on V. Because it's running as a full program,
it will return its results (instead of going into a sulk). D can, of
course, be an appropriate version of LoopIfHalts :-)

Any extra input that P requires can be given by D.

Simon

Relevant Pages

  • Re: Psychology of arguing with people
    ... >>posts that someone like Peter Olcott is never going to be able to ... detracts from the conversation. ... are slippery in mathematics is not exactly wrong (there is ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed
    ... Peter Olcott says... ... Peter, as I've already said, nothing in mathematics can ... Why do you think this program has pathological self-reference? ... L "LoopIfHalts" and calling H "WillHalt" changes things? ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... >>Peter Olcott says... ... It's about mathematics and mathematical stuff. ... (perhaps by having an ordinary UTM, U, as part of D, and having U ... be an appropriate version of LoopIfHalts :-) ...
    (comp.theory)