Re: What is the Result from Invoking this Halt Function?

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/12/04 

Date: Thu, 12 Aug 2004 00:53:31 GMT

"Simon G Best" <s.g.best@btopenworld.com> wrote in message news:411A40D8.8040100@btopenworld.com...
> Although I said I intended not to respond anymore, I am failing to
> resist the temptation to respond.
>
> However, I shall attempt to include everything I wish to say at this
> time in this one post, as I do not wish to resume contributing to the
> clutter in these newsgroups.
>
> Peter Olcott wrote:
> > "Simon G Best" <s.g.best@btopenworld.com> wrote in message news:4118E438.90806@btopenworld.com...
> >
> >>Substantiate your claims.
> >>
> >>Provide a way for a Turing Machine to be able to determine whether or
> >>not it was invoked as part of another Turing Machine, and we'll see if
> >>it supports your claim to have refuted Turing's proof.
> >>
> >>Substantiate your claims.
>
> > This is now published on my website
> > www.halting-problem.com
>
> The first thing to note is that the stuff on your website is not very
> clear. I have noticed that some other respondents (as did I at first)
> have taken the part which says, "/it/ merely looks up the action
> associated with the state in /its/ state transition matrix table"
> (emphasis mine), to mean that the modified UTM is looking at the "state
> transition matrix table" of the modified UTM /itself/. What you
> actually meant is that it looks at the "state transition matrix table"
> for the /simulated/ TM.

Nope that is not it. I must have the UTM tell me that it has no other
state transitions that would be pending after the Halt function would
execute its final state transition. I was envisioning the UTM as using
its own tape and state transition matrix to directly execute any other
TMs. This would mean that the execution of the UTM, and any
other TM that it is invoking would form a single integrated finite
automaton. As long as I know:

(1) That there is no UTM state transition out of the halt analyzer's final state
(the one that write the ONE to the tape).

(2) The only state transition out of the halt function's final state is a sequence
of state transitions (with no conditional or unconditional branches) that end
in the UTM's final state.

The UTM can easily provide this information from its own state transition
matrix table.

> The second thing to note is that you've left out various pieces of
> information, such as how the inputs to your alleged halt-analyzing TM,
> and to your modified UTM, are to be given. I'll assume that the alleged
> halt-analyzing TM takes a TM description (of the TM to be analyzed) and
> an input description (of the input that would be given to the TM to be
> analyzed) as input, and that your modified UTM also takes a TM
> description (of your alleged halt-analyzing TM) and input description
> (of the input to be given to your alleged halt-analyzing TM) as input.

Its the same as always, all this stuff is assumed to already be on the tape.

> In particular, you have not said /how/ a simulated TM, M, would actually
> /ask/ your modified UTM about its own state transitions. Neither have

This would just be a little mini TM that is an intregral part of the UTM.
The Halt function would know its own final state (the one that would
either write the SPACE or the ONE to a specified tape location).
It could merely ask the UTM:

if (TheStateAfterThisStateIsTheUTMsFinalState(HaltFunctionFinalState))
   WriteToTapeLocation(LocationNumber, ONE);
else
   WriteToTapeLocation(LocationNumber, SPACE);

> you said /how/ your modified UTM would /answer/. You've indicated that
> your modified UTM would examine the "state transition matrix table" of
> M, but you've left out the /vital/ mechanisms for M to be able to
> request this information, and for your modified UTM to be able to
> provide it to M. You really do have to stop making these significant
> omissions if you want to be taken seriously. While such significant
> omissions remain, your claim to have refuted Turing's proof remains
> unproven, and Turing's proof remains unrefuted.
>
> Now, onto the actual debunking of your claimed 'solution'.
>
> Notation:
> Throughout this, I shall use '<x>' to mean 'an appropriately encoded
> description of x', where x could be a Turing Machine, or input to be
> given to a Turing Machine. '<<x>>', therefore, means 'an appropriately
> encoded description of an appropriately encoded description of x'.
>
> Notation:
> Throughout this, I shall use '(x)' to mean 'input consisting of x, where
> x may be a single argument, or an appropriately formatted list of
> arguments.' I shall use 'h, t' to mean 'a list of arguments, where h is
> the first argument, and t is either an argument, or a list of
> arguments.' (For example, 'a, b, c' is itself a list of the three
> arguments, a, b, and c, in that order. '(a, b, c)' is an appropriately
> formatted list of those arguments (as they would all have to go on the
> same tape, somehow).)
>
> Example:
> '<(x)>' means 'an appropriately encoded description of input consisting
> of x'.
>
> Notation:
> Throughout this, I shall use 'M(x)' to mean 'the output produced by TM M
> when given input (x)'. If M doesn't halt, M(x) is undefined. ('M(x)'
> is not to be confused with giving input (x) to M. If M(x) is undefined,
> that doesn't mean we couldn't give M the input (x), it just means
> there's no output (not even a blank tape). In other words: if M would
> not halt on (x), M(x) is undefined.)
>
> Notation:
> I shall use C-style string literals to refer to literal tape contents.
> For example, "abc\"" means that the contents of the tape literally
> consists of the sequence of symbols 'abc"'.
>
> Now that we've got that notation sorted out, let's get down to business.
>
> You're modifying a Universal Turing Machine (UTM), so that a Turing
> Machine (TM), M, that is being simulated by it, can ask it whether or
> not particular internal states of M have further state transitions
> defined for them. I'll call your modified UTM 'V'.
>
> However, you have not actually said /how/ a TM, M, would go about
> /asking/ V for such information, or /how/ V would /provide/ M with its
> answer. Although I can conceive of such a mechanism myself, I shall not
> presume what your mechanism would be. Consequently, some of the
> following will be a bit klunky, as I'm having to work around that
> significant omission of yours.
>
> I'll call your alleged halt-analyzing TM 'P'. P takes input (<M>, <x>),
> where: M is the Turing Machine to be analyzed; and x is the input that
> would be given to M. If M would halt on x, and P is 'invoked directly'
> in V's simulation, P(<M>, <x>) = "1". If M would not halt on x, and P
> is 'invoked directly' in V's simulation, P(<M>, <x>) = "0". (That's a
> bit of a klunky way for me to put it, but you haven't said what V's
> 'asking' and 'answering' mechanisms actually are.)
>
> V can itself be simulated by an unmodified UTM, U. U takes input (<V>,
> <(<M>, <x>)>), where: M is the Turing Machine to be simulated by V; and
> x is the input to be given to V.
>
> We can now use U to simulate 'direct invocations' of P.
>
> A 'direct invocation' of P can be simulated by giving U the input (<V>,
> <(<P>, <(<M>, <x>)>)>), where: M is the TM to be analyzed by P; and x is
> the input that would be given to M. When given this input, U will
> simulate V when V is given the input (<P>, <(<M>, <x>)>). The simulated
> V will then simulate P when P is given the input (<M>, <x>).
>
> U is an /unmodified/ UTM. V has no way of knowing that it itself is
> being simulated. If U is /itself/ part of another TM, Q, V has /no way/
> of finding this out. This is the fatal flaw in your 'solution'.
>
> With U, V and P, we can now define another Turing Machine, Q, which
> contains U as a part of itself. Q operates in the following, two stages.
>
> Q takes input (<M>, <x>), where: M is the TM to be analyzed by P; and x
> is the input that would be given to M. The first stage of Q processes
> the input (<M>, <x>) to become the 'input' for the second stage, (<V>,
> <(<P>, <(<M>, <x>)>)>).
>
> The second stage of Q is for Q to process (<V>, <(<P>, <(<M>, <x>)>)>)
> as U. U simulates V on (<P>, <(<M>, <x>)>), and V simulates P on (<M>,
> <x>). P asks V about its state transitions, and V answers.
>
> As P is being simulated on V as a 'directly invoked program', with no
> modifications having been made to P at all, V tells P that all those
> states which are intended to be final states really are final states.
> As a result, P returns its results, P(<M>, <x>), as if it had been
> invoked directly.

What all you guys fail to realize is the proper way to form a refutation.
The original proof proposed to cause the halt analyzer to return incorrect
results in every possible instance of a certain input. It did this by creating
one possible input that was proposed to be impossible to correctly process.

What you are proposing is not a method that makes my method fail in every
possible instance. What you are proposing is a method that will make my
method fail in one instance. In every case where you are not applying your
method to my method, my method succeeds. If there exists even the possibility
of applying my method without your method, then you have not refuted
my method.

You can't just show how you can screw up my method to refute me.
You must show a way to screw up my method that can not possibly ever
be circumvented. In other words if my method could not exist without
also implementing your method, then you have refuted me. If my method
can possibly exist without your method, then you have merely shown
yet another way to NOT solve the Halting Problem.

> V returns this result, P(<M>, <x>), as its own result to U (the second
> stage of Q), and U returns this result as its final result. Q does no
> further processing, and so P(<M>, <x>) is Q's final result.
>
> If P is a halt-analyzing TM, then it /must/ *always* return results when
> 'directly invoked'. As can be seen above, P would *always* return
> results to Q, and Q would *always* return *exactly the same results*
> (because all it does is leave P's results unchanged on the tape).
> Therefore, if P is a halt-analyzing TM, then Q is also a halt-analyzing
> TM which *always* returns its results *regardless of whether or not Q is
> itself part of another TM*.
>
> Turing proved that Q cannot exist. Therefore, it must be that P cannot
> exist.
>
> One thing for you to learn from this is that UTMs can /always/ be used
> to foil your attempts to refute Turing's proof. (That's not the only
> thing you need to learn, though.)
>
> Please move on to trying to disprove the Church-Turing Thesis, so that I
> can learn more about it from your many respondents :-)
>
> Simon
>

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... I must have the UTM tell me that it has no other ... its own tape and state transition matrix to directly execute any other ... That there is no UTM state transition out of the halt analyzer's final state ... (the one that write the ONE to the tape). ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... >>another Turing Machine, or invoked independently of any other Turing ... This information is very easy for the UTM to provide, ... >>looks up the action associated with the state in its state transition ... >>What if Halt is not running on a UTM? ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... >>another Turing Machine, or invoked independently of any other Turing ... This information is very easy for the UTM to provide, ... >>looks up the action associated with the state in its state transition ... >>What if Halt is not running on a UTM? ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... I must have the UTM tell me that it has no other ... > its own tape and state transition matrix to directly execute any other ... > That there is no UTM state transition out of the halt analyzer's final state ... > (the one that write the ONE to the tape). ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... I must have the UTM tell me that it has no other ... > its own tape and state transition matrix to directly execute any other ... > That there is no UTM state transition out of the halt analyzer's final state ... > (the one that write the ONE to the tape). ...
    (sci.logic)