1
$\begingroup$

In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:

I find that at least one further phenomenon seems to be identifiable and either universal or remarkably common, namely, ordering (regularity or periodicity) in the time dimension... [It] is noteworthy that all computing machines use temporal pulsing.

As far as Turing machines go, this is true since there is a fundamental "time step" during which a symbol is read, the state is changed, and the read/write head moved. But this got me wondering: are there any non-Turing computing proposals without this fundamental time step?

$\endgroup$
2
$\begingroup$

There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC).

Shannon's original formulation of GPAC could not compute certain functions, including the Gamma function. However, a 2007 paper cited in that Wikipedia article provides a reasonable reinterpretation of GPAC which turns out to be more powerful, enough so that the authors claim that "the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals."

Claude Shannon is well-known as a pioneer in digital computer design and particularly for his foundational work on information theory, but his genius and sense of whimsy led him to extraordinary achievements in other areas, and analog computation remained an interest throughout his life. One example is his mathematical analysis of juggling, including the construction of a prototype juggling robot. (See here for more information and a brief video including the robot.)

$\endgroup$
0
$\begingroup$

Not all computing machines use temporal pulsing. Turing machines don't.

What is more, not all computing machines perform all steps in order: asynchronous circuits don't. Distributed systems don't.

I believe the author is mixing up

  1. computing as a discrete (stepwise) process
  2. strictly sequential computing, in which no steps are executed concurrently
  3. clock-based computing, in which steps happen in sync with a clock

You often have the first without the second, or the second without the third.

Modern CPUs use pipelining, in which steps do not happen in sequence. Modern software systems use pipelining in the large, in which multiple data processing units are combined into data flow networks or other types of communicating computational systems.

Strictly sequential, one-processor, one-instruction-at-a-time computing is conceptually simple and therefore attractive to theorists, educators, and people who want to build simple systems. Turing machines work that way. They are an example of the second type of system; they don't involve time, but they do perform their steps in strict sequential order.

As galdalf61 writes, the notion of algorithm is often limited to such strictly sequential computation. That doesn't mean actual computational machines or systems all work that way; they don't.

Similarly, basing everything on a clock makes digital circuitry easier to design, and it happens often, but not always.

$\endgroup$
2
  • $\begingroup$ I think asynchronous circuits might be closest to what I was wondering about. Is there any overall theoretical framework for their analysis, or is it ad hoc at this point? $\endgroup$
    – Andrew
    Sep 12 '19 at 16:49
  • $\begingroup$ I am familiar with several formalisms for describing and/or verifying concurrent systems, but nothing specifically for the design of such circuits. $\endgroup$ Sep 27 '19 at 7:51
-1
$\begingroup$

The concept of sequentially performing one step after another seems to be inherent in our intuitive understanding of what constitutes an "algorithm", so it is present in one form or another in all useful models of digital computing. Even in a non-deterministic Turing machine, which can make multiple copies of itself at each step, each individual copy still executes its steps sequentially.

You can envisage a non-sequential "oracle" model which just "knows" the answer to every request/problem sent to it, and responds with that answer immediately - but that is not modelling what we understand an algorithm to be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.