[PO] Re: Can a regular Turing Machine provide Protected Memory?

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

Date: Sun, 29 Aug 2004 20:56:40 +0000 (UTC)

Would you like to see my 'halt analyzer'? It's a real TM!

Mitch Harris wrote:
> In article <ug8902-euu.ln1@lexi2.athghost7038suus.net>,
>
>>As it is, his current method apparently requires TMs to determine
>>whether they are being called from a Halting Analyzer. How
>>TMs do that without call instructions, I've no clue.
>
> They can't. But in some sense, it doesn't matter. Just assume that it can
> be done, and see what the consequences are. What those consequences are
> ...I don't think that has been established here.

He is, or was, relying on his augmented 'TM's running on (being
simulated by) an augmented 'UTM'. The augmented 'UTM' is itself an
ordinary, /real/ TM (though his augmented 'TM's that run on them aren't
(though obviously can't compute anything that real TMs can't compute,
otherwise they won't be able to run on his 'UTM')).

So, we can just treat his 'UTM' as the Turing Machine that it is, and
his augmented 'TM's that run on it as just some of the input to be given
to it. And with that part of the input always being the same (it being
his mythical halt analyzer), we can just treat it as being a part of the
input encoding convention (we always need a way to format the arguments
in the input, somehow).

As a result, his 'UTM' is really just the plain old ordinary
halt-deciding TM that the classic proof directly proves the nonexistence
of (assuming that the input encoding function is itself, in principle,
Turing-computable).

But then again, maybe his 'UTM' /can/ exist (it's not difficult to
imagine there being such a TM, simulating things like protected memory,
and so on). But that would just mean that the input encoding convention
is not itself Turing-computable.

An example of a similarish input encoding convention would be one which
encodes each TM-input pair (to be 'analyzed'), (M, x), as a number, n,
represented as a contiguous sequence of n 1s on the tape, with the
amazingly useful property that each (M, x) where M would halt on x gets
encoded as an odd n, and each (M, x) where M would not halt on x gets
encoded as an even n.

The 'halt analyzer' TM would then only need to have the following state
transitions:-

         Current Scanned Printed Head Next
         state symbol symbol move state
         ------- ------- ------- ---- -----

         q_1 ' ' '0' N q_3
         q_1 '1' ' ' R q_2

         q_2 ' ' '1' N q_3
         q_2 '1' ' ' R q_1

with q_1 as the initial state, and q_3 the halting state. With an odd
number of 1s on the tape (the first 1 being placed under the head at the
start), this TM outputs a single 1, indicating that M halts on x. With
an even number of 1s, a single 0 is output, indicating that M does not
halt on x.

Unfortunately, the required input encoding convention is not
Turing-computable.

With the input encoding convention not being Turing-computable, Loopy
Faults won't be able to use this 'halt analyzer', as it won't be able to
compute the input to be provided to its 'halt analyzer' stage. So, we
can't actually construct Loopy Faults, and can't do the classic Loopy
Faults proof.

Neither can we actually use this 'halt analyzer' ourselves without using
a more powerful model of computing for the process of encoding the
input. But then we're /really/ solving the Halting Problem for Turing
Machines by using that more powerful model of computing, and that, as
they say, is another story.

:-)

Simon

Relevant Pages

  • [PO] Re: Can a regular Turing Machine provide Protected Memory?
    ... Would you like to see my 'halt analyzer'? ... >>TMs do that without call instructions, ... But that would just mean that the input encoding convention ... But then we're /really/ solving the Halting Problem for Turing ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > only way to construct a halt analyzer, his proof did not show that constructing ... However, as WillHalt, you do not know who or what gave you this tape. ... As a Turing Machine, you simply do not know who ... invokes you, you would return 'false', and LoopIfHalts would then halt. ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > only way to construct a halt analyzer, his proof did not show that constructing ... However, as WillHalt, you do not know who or what gave you this tape. ... As a Turing Machine, you simply do not know who ... invokes you, you would return 'false', and LoopIfHalts would then halt. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... > faintest idea what method Turing used. ... requires the halt analyzer to return its results to every caller. ... > you accept that diagonalisation is valid, and as you also accept that ... > What do you mean 'the pure math version'. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... > faintest idea what method Turing used. ... requires the halt analyzer to return its results to every caller. ... > you accept that diagonalisation is valid, and as you also accept that ... > What do you mean 'the pure math version'. ...
    (sci.logic)