Re: Turing Machines and Physical Computation

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 11/29/04 

Date: Mon, 29 Nov 2004 02:13:14 GMT

"JXStern" <JXSternChangeX2R@gte.net> wrote in message
news:sc3kq0ddbo067s603odkpl3ppqmdo0noma@4ax.com...
> On Sun, 28 Nov 2004 08:14:01 GMT, "Stephen Harris"
> <cyberguard1048-usenet@yahoo.com> wrote:
>>>... But,
>>> before a mark constitutes anything interesting, it must have a
>>> subject, I stand by that.
>>
>>Is the future something that you can grasp either with your mind or
>>with your hand? With your mind you can't do better than make
>>predictions which sometimes come true. In mathematics, perhaps
>>the successor function, n +1, n +2, n + 3 and so implies a future.
>>
>>A succession of causes and effects, manifested as events, unfold
>>to our perception which take time. What is the physical thing ...
>
> I'm not sure what the question is you have in mind here, but you said
> the magic word(s), "cause" and "time".
>
> What are the proper roles of causality and of time in the world of
> Turing Machines? Seems to me that many mathematicians see TMs as
> outside of time and such logical results as TMs present as being
> immanent.
>

> Part of the system that must constitute any theory of phyiscal
> computation, I assert, is going to have to be a recognition of time as
> a dimension and causality as everywhere manifest.
>

I think that is correct. It is put forth in the Church-Turing Thesis
rather than adumbrated in that 1936 Turing paper On Computable ... per se.

I am going to quote this part again because it mentions the role of
the memory/storage is seperate from the device. In the 1936 paper
the memory/storage is a hypothetical potentially infinite tape.

"(Note that this formulation has implicit in it the idea that memory/storage
is separate from device; any actual computer has finite memory, but the
formulation always assumes that memory can be added at will.)"

SH: The TM tape allows finite calculations of great length, already having
all the memory it will ever need to compute some finite problem. A physical
computer will run out of memory for some huge calculation. Yes you can
add memory to the physical computer. But there is some point where all
the physical memory in the universe will only store some huge finite amount
of information or number of digits. Because Turing's tape is not actually
physical it can store a huge number of digits that is twice or three times
etc.
greater than that of the physically limited computer. The values are still
finite
in both cases, but not equal. The TM is also not required to complete its
calculation within a given time limit. The problems computed by both a
TM and PC are of the same type---computable. My description does
not mean that a new class of computation beyond a computable function
has been posited. Like a new class is posited by those Super-Turing machines
that go beyond Turing computable. Also quantum computers, if they can
build them, will solve some problems due to better speed that a PC will
never finish, but AFAIK, the type of problem and quantum computation
is still not greater than or beyond turing computable. I've seen the
definition of a quantum turing computer come with an infinite tape also.

>From Wikipedia, the free encyclopedia.
"In the computability theory the Church-Turing thesis, Church's thesis,
Church's conjecture or Turing's thesis, named after Alonzo Church and Alan
Turing, is a hypothesis about the nature of mechanical calculation devices,
like computers, and what kind of algorithms they can calculate.

It is generally assumed that an algorithm must satisfy the following
requirements:

  1.. The algorithm consists of a finite set of simple and precise
instructions that are described with a finite number of symbols.
  2.. The algorithm will always produce the result in a finite number of
steps.
  3.. The algorithm can in principle be carried out by a human being with
only paper and pencil.
  4.. The execution of the algorithm requires no intelligence of the human
being except that which is needed to understand and execute the
instructions.
An example of such a method is the Euclidean algorithm for determining the
greatest common divisor of two natural numbers.

The notion of algorithm is intuitively clear but is not formally defined
since it is not exactly clear what a "simple and precise instruction" is,
and what exactly the "required intelligence to execute these instructions"
is. (See for example effective results in number theory for cases well
beyond the Euclidean algorithm.)

Informally the thesis states that our notion of algorithm can be made
precise (in the form of computable function) and computers can run those
algorithms. Furthermore any computer can theoretically run any algorithm,
that is the theoretic computational power of each computer is the same and
it is not possible to build a calculation device which is more powerful than
a computer. (Note that this formulation has implicit in it the idea that
memory/storage is separate from device; any actual computer has finite
memory, but the formulation always assumes that memory can be added at
will.)"

SH:There is a physical limit to the amount of memory that can be added at
will.

> This is not a matter of future, though, it is a matter of how the now
> relates to the other-than-now. Physical computation depends on some
> kind of time-binding, it seems to me, if that statement is not
> hopelessly metaphysical. Purely abstract TMs do not require time, I
> guess, and certainly one can play with nondeterministic machines that
> do not even require order.
>
> Then there's my man Wittgenstein who pretty much hated the idea of
> mathematical sequences. He was dead wrong in this, I believe, and it
> was perhaps this one point of his that kept him from appreciating to
> even the smallest degree what Turing was doing under his very nose.
>
> J.
>

I read both his early Tractucus? and later Philosophical Investigations?

The writings that the philosophers state Wittgenstein changed his positions
between early in life and later in life. I find that remarkable. I didn't
get into his philosphical views on mathematics that I can remember, but
language.

Regards, Stephen

Relevant Pages

  • Re: Turing Machines and Physical Computation
    ... rather than adumbrated in that 1936 Turing paper On Computable ... ... any actual computer has finite memory, ... computer will run out of memory for some huge calculation. ... It is generally assumed that an algorithm must satisfy the following ...
    (sci.math)
  • Solving the memory issue of lock-free algorithms
    ... I read a lot about lock-free algorithm and tried to find an "elegant" ... solution to the memory problem that the algorithms poses. ... LFStackNode *Next; ... xor eax, eax ...
    (comp.programming.threads)
  • Re: Version after Version
    ... MMX, by doing 50 times two additions at a time. ... Many compilers & memory managers have at least the option to align data on ... > - compression and decompression works at the Bit level ... > LZW is the until recently proprietory algorithm of Uinisys ...
    (alt.comp.lang.borland-delphi)
  • Re: Sans memory barrier native thread communication upon AMD64?
    ... producer/consumer or a distributed algorithm w/ mutual ... that may be garbage collected independent of any other native thread. ... microthread allocates its environment (including dynamic stacks) from the ... system provides a thread safe memory allocator. ...
    (comp.programming.threads)
  • Re: misconceptions on computer science
    ... >> Show me an algorithm that is beautiful but useless. ... You haven't given a single example that furthers your position. ... >> What specific thing that Turing did are you talking about? ... Because those sound like engineering projects to me. ...
    (comp.object)