Re: Turing Machines and Physical Computation

From: Albert van der Horst (albert_at_spenarnc.xs4all.nl)
Date: 12/06/04 

Date: 06 Dec 2004 21:38:09 GMT

In article <cnvv6k$aak$1@msunews.cl.msu.edu>, <stephen@nomail.com> wrote:
>In sci.math JXStern <JXSternChangeX2R@gte.net> wrote:
>: On Tue, 23 Nov 2004 05:50:40 GMT, "Stephen Harris"
>: <cyberguard1048-usenet@yahoo.com> wrote:
>:> Definition: Common term for "computer", usually when considered at
>:>the hardware level. The Turing Machine, an early example of this usage, was
>:>however neither hardware nor software, but only an idea.
>:>http://www.hyperdictionary.com/dictionary/machine
>
>: It was a gedankenexperiment, and eminently realizable in physical
>: form, purposely so, to answer Hilbert's #10.
>
>: Someone remind me, are there any TM results that depend on an infinite
>: tape for positive results?
>
>: J.
>
>Sure. Can the language a^n b^n for n>=0 be recognized by a Turing
>Machine, or recognized at all. If you only have a finite tape
>than there are members of this language you cannot recognize.

The wording is a bit metaphysical.
This problem is such that for each N there is an instance of
a language item wherefore a dedicated TM will need a tape
that is larger than N.
Actual infinity doesn't enter the picture.

That there are probably values of N this universe can't cope
with 1) (though we don't know enough of this universe to actually
pin down numbers) is irrelevant to the mathematical analysis.
I really can't see why Plato should rear his ugly head in
this context.

1) If and when some one ventures to make a physical model of
a Turing machine.

>
>Stephen 

-- 
-- 
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
        One man-hour to invent,
                One man-week to implement,
                        One lawyer-year to patent.

Relevant Pages

  • Re: turing completeness
    ... The tape doesn't have to be "infinite" once and for all. ... The Turing Machine just needs to be able at will to drive to CompUsa ... The ultimate bound of the simulation is physical ... if a language says that no more than 4 GB ...
    (comp.programming)
  • Re: Turing Machines and Physical Computation
    ... If you only have a finite tape ... >than there are members of this language you cannot recognize. ... That there are probably values of N this universe can't cope ... a Turing machine. ...
    (sci.math)
  • Re: What is complexity?
    ... >>>printing on the data tape, it will use an infinite length of tape. ... >>I was NOT talking about the Turing machine as a mathematical abstraction. ... >>In the real universe, time passes, and operations take time. ...
    (talk.origins)
  • Re: My Problem | What is right for ...
    ... no implementation of either language is Turing Complete. ... A Turing Machine has an infinitely long tape, ...
    (comp.lang.c.moderated)
  • Re: [QUIZ] The Turing Machine (#162)
    ... tape = tape ... The Turing Machine ... The three rules of Ruby Quiz 2: ... An infinite tape of memory cells that can hold one character ...
    (comp.lang.ruby)