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

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/30/04 

Date: Mon, 30 Aug 2004 09:52:19 +0200

Peter Olcott wrote:
> "Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2p8uuuFi1k3eU1@uni-berlin.de...
>
>>Peter Olcott wrote:
>
>
>>- protected memory is sorta like read only memory.
>> - so yeah you can interleave processes in such a way that
>>they don't screw up each others memory
>>
>>- These capabilities provably don't allow you to compute any
>>more functions than you can with plain old vanilla TMs.
>>(er..I said that already with the TFAE).
>
> If the Halt Analyzer stores the value of TRUE (1 or 0)
> in a single bit of protected memory that no other TM
> has access to, then it can determine whether or not
> any TM halts, and return this result to every caller,
> without undecidability.
>
> If you don't agree with this please try to provide a
> specific and detailed scenario that forms the single
> required counter-example showing why this is not
> true.

1) I don't agree

2) the reason is because it is not within the rules of logic
to restrict the Halt analyzer -unless you are restricting
-all- machines similarly-. Within the proof by
contradiction, you first assume that you have -a- Halt
analyzer (you don't care how it is constructed, it can use
any any any possible weird properties of TMs, anything you
can come up with. Whatever those weird properties you use,
the proof doesn't even consider them (it doesn't need to),
it just uses the property that it is -supposed to- compute
the Halt function. This assumption is then shown to cause a
contradiction.

Just giving one particular trial Halt analyzer some special
properties doesn't have any consequences at all. Because the
only property of any assumed Halt analyzer that is used is
that it is a -correct- Halt analyzer. Since this assumption
causes a contradiction, it must be false.

If you make a specific property requirement of a Halt
analyzer, then you are essentially making that requirement
of -all- the machines you are talking about. And at that
point, sure it is possible that the halting problem for that
new kind of machine is solvable. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages

  • Re: [PO] Can a regular Turing Machine provide Protected Memory?
    ... >>more functions than you can with plain old vanilla TMs. ... > in a single bit of protected memory that no other TM ... contradiction, you first assume that you have -a- Halt ... Just giving one particular trial Halt analyzer some special ...
    (comp.theory)
  • Re: [PO] halting problem reading comprehension
    ... >mention that this could be used as input to a Halt Analyzer, ... I can use write only memory. ... >> David C. Ullrich ...
    (comp.theory)
  • Re: [PO] halting problem reading comprehension
    ... >mention that this could be used as input to a Halt Analyzer, ... I can use write only memory. ... >> David C. Ullrich ...
    (sci.logic)
  • Re: [PO] halting problem reading comprehension
    ... | than merely a way to break my Halt Analyzer. ... I can use write only memory. ... be able to detect every other program which is also a halt detector. ... Hence your version of the halting program will have to give up if it is ...
    (comp.theory)
  • Re: [PO] halting problem reading comprehension
    ... | than merely a way to break my Halt Analyzer. ... I can use write only memory. ... be able to detect every other program which is also a halt detector. ... Hence your version of the halting program will have to give up if it is ...
    (sci.logic)