Re: Troll-debility sets in [was: What is the Result from Invoking this Halt Function?]

From: Martin Shobe (mshobe_at_sbcglobal.net)
Date: 08/22/04 

Date: Sun, 22 Aug 2004 13:53:39 GMT

On Sun, 22 Aug 2004 07:22:49 GMT, Owen Jacobson
<angstrom@lionsanctuary.net> wrote:

>On Sat, 21 Aug 2004 23:55:00 +0000, Simon G Best wrote:
>
>> >parr(*> wrote:
>>
>>> It could be that since Turing, work has been done to define a
>>> Turing-like Machine which handles asynchronous inputs, and can therefore
>>> be analysed mathematically. If there is, I'm sure someone will let me
>>> know and I can eat humble pie.
>>
>> What, exactly, do you mean by "asynchronous inputs"? Do you just mean
>> things like 'interactive' inputs? Or do you mean something which a
>> clocked state-machine would not be able to "handle"?
>
>Consider an asychronous keyboard handler triggered by a hardware
>interrupt that adds one to a value each time a keystroke is recieved. A
>program that simply reads this value over and over and never writes to it
>will nonetheless see this value climb unpredictably over time. This
>behaviour, a stored symbol changing without ever being written, is outside
>the definition of a Turing machine.

There are a number of things that can be done with computers that
can't be done with Turing machines. Interactive input, displaying
information on a screen, examining your own code, multithreading, etc.
However, any *computation* done by a computer can be done by a Turing
machine. In this case, you have to give results of each read of the
counter as input to TM.

Martin

Relevant Pages

  • Re: Troll-debility sets in [was: What is the Result from Invoking this Halt Function?]
    ... On Sun, 22 Aug 2004 07:22:49 GMT, Owen Jacobson ... >Consider an asychronous keyboard handler triggered by a hardware ... >the definition of a Turing machine. ... There are a number of things that can be done with computers that ...
    (sci.logic)
  • Re: The Demise of Computationalism?
    ... anyone would actually implement the thing as a Turing Machine. ... It remains to be seen whether UTMs simulate ordinary TMs by executing programs. ... I think you make an important conceptual point: there are significant differences in the way UTMs produce their output vis a vis the way ordinary digital computers do. ... The class of UTMs are just regular old Turing Machines that happen to have ...
    (comp.ai.philosophy)
  • Re: Turing machines, quantum computers, and alephs
    ... If you have marked up the solution to the halting problem for all Turing ... do we know that for every non-halting Turing machine ... is the Turing-Church thesis to 'computational power' in the first place? ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... If you have marked up the solution to the halting problem for all Turing ... do we know that for every non-halting Turing machine ... is the Turing-Church thesis to 'computational power' in the first place? ...
    (comp.programming)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... Owen Jacobson wrote: ... >>08) void LoopIfHalts(string SourceCode, string DataInput) ... WillHalt, but does *not* include line 16. ... > cannot be a Turing machine. ...
    (comp.theory)
Loading