Scrutiny on the definition of the Turing Machine?

Question

Wiki states:

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

Has this intuitive notation where one "manipulates symbols on a strip of tape" been examined and scrutinized? For example, if I perform a computation with a "strip of electric fields in space" work effectively the same as a "strip of tape" is it a different Turing machine? How about a spinor field instead?

My concerns are these have different time evolution laws. For example the time evolution of the electric field is given by Maxwell's equations, spinor's by Dirac or Klien Gordon for spin-0 particles. So it's not obvious to me they will have the same computational prowess.

I am questioning: philosophically whether TMs accurately model effective computation. Has someone addressed this before?

Answer 1

... the time evolution of the electric field is given by Maxwell's equations ... so it's not obvious to me they will have the same computational power

I think the underlying distinction you're trying to capture here, but maybe couldn't formally articulate, is the difference between analog and digital computation. Philosophically, maybe take a look at David Chalmers' http://consc.net/notes/analog.html

All computers map input from an input space to output in an output space. Both input and output for digital computers consists of finite strings of symbols from a finite alphabet, which can be mapped to integers by Godel numbering (or other schemes), whereby we're talking about functions of the form f:N-->N. But not all such functions are computable. Others have mentioned the Church-Turing thesis, that all models of (digital) computation result in exactly the same class of computable functions. So digital models of computation are all equivalent.

But integers N are countably infinite, whereas your electric field (and other) example is probably trying to suggest an uncountable input/output space, like the real or complex numbers, etc. At least that's what I'm guessing you were trying to get at. And then we're talking about analog computation, which is indeed a whole different ball of wax, but much less comprehensively studied than digital, e.g., https://arxiv.org/pdf/1805.05729.pdf and https://www.eetimes.com/analog-computer-trumps-turing-model/, etc.

Answer 2

Short Answer

Yes. Absolutely. Philosophers wrestle over these sorts of phrases to tackle the metaphysics of computation endlessly.

Long Answer

Since 1936, the notion of Turing machines and effectively computable (and several similar phrases used by Hilbert, Goedel, Kleene, Post, and others) has been the object of much thought and discussion. Ultimately, the topic is foundational for philosophies that address logico-mathematical computation. The discussion has also been broadened philosophically beyond logical and mathematical computation to physical computation, which is viewed as a broader exploration of the relationship of computation within physicalism.

A good place to start to understand physical computation is Computation in Physical Systems (SEP). From the article referring to the Church-Turing Thesis (CTT):

Bold Physical CTT can be made more precise in a number of ways. Here is a representative sample, followed by references to where they are discussed:

1. Any physical process can be simulated by some TM (e.g., Deutsch 1985, Wolfram 1985, Pitowsky 2002).
2. If a physical system can be modeled by a certain kind of idealized computing machine that manipulates real-valued quantities, then that physical system can only compute Turing-computable functions on denumerable domains (Blum et al. 1989 show this to be false).
3. Any system of equations describing a physical system gives rise to computable solutions (cf. Earman 1986, Pour-El 1999). A solution is said to be computable just in case, given computable real numbers as initial conditions, it returns computable real numbers as values (where, following Turing, a real number is said to be computable just in case there is a TM whose output produces any desired number of digits of that number).
4. For any physical system S and observable W, there is a Turing-computable function f: N → N such that for all times t ∈ N, f(t) = W(t) (Pitowsky 1990).

Remember, the a-machine (Turing machine) is an abstract model originally based on the notion of personal (that is human) computation with the aid of a pencil and paper, and embraces human intuition to an extent, at least by an escape from it. And the Church-Turing Thesis was coined a thesis precisely because it rests on ambiguous or pre-theoretic ideas and definitions. That gives philosophers a lot of wiggle room to evaluate the Turing machine and effective computability.

Ultimately, there are thinkers such as Chalmers, Cummins, and others who seek to put forth definitions of physical computation that surround the Turing machine theoretically, and extend an understanding. One such work is Oron Shagrir's The Nature of Physical Computation in which he puts forth a view of physical computation that is termed a semantic view. On page 26, he begins a chapter entitled "Turing's Computability" that dissects the history and theory.

Answer 3

A Turing machine is a finite-state control equipped with an external storage device in the form of a finite tape that can be extended indefinitely in both directions (e.g., Moll, Arbib, Kfoury: An Introduction to Formal Language Theory. Springer 1988)

Hence a Turing machine has a finite alphabet, and the tape can be extended indefinitely by adding blanks at either end.

The physical realization of the tape is not specified. I do not know whether anybody has problematized your question before. But before, I consider necessary to quantify what you mean by

‚different time evolution laws‘.

The basic theorem of language theory states that those languages which can be specified by a grammar are exactly those, which are accepted by a Turing machine (see Chomsky hierarchy).

The time characteristic of the calculation by a Turing machine is not a relevant quantity: Neither the duration of a single step, nor the amount of necessary steps has any impact on the class of acceptable languages of a Turing machine.

Also if one relaxes the number of tapes or considers non-deterministic Turing machines: The class of acceptable languages does not change.

Answer 4

The Turing machine does not model time; it only models the number of steps required to execute an algorithm, therefore changing the physical properties of the machine in order to change how long a step takes has no affect on the Turing Machine model. A Turing Machine can be implemented with the fastest possible electronics or with a turtle that lumbers up and down a line of stones, moving the position of each stone to indicate a particular letter, and it's the same Turing machine.

Adding time to the formalism makes it a more powerful formalism in some sense because there are a few (not many) things that change. For example, suppose you have a Turing machine where the first step takes one second and each subsequent steps takes half as long as the previous step. Then you can do an infinite number of steps in two seconds, and this gives you a machine that is more powerful than a Turing Machine. Of course, this machine also can't be implemented...