Zeno machine

Last updated

In mathematics and computer science, Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model related to Turing machines that are capable of carrying out computations involving a countably infinite number of algorithmic steps. [1] These machines are ruled out in most models of computation.

Contents

The idea of Zeno machines was first discussed by Hermann Weyl in 1927; the name refers to Zeno's paradoxes, attributed to the ancient Greek philosopher Zeno of Elea. Zeno machines play a crucial role in some theories. The theory of the Omega Point devised by physicist Frank J. Tipler, for instance, can only be valid if Zeno machines are possible.

Definition

A Zeno machine is a Turing machine that can take an infinite number of steps, and then continue take more steps. This can be thought of as a supertask where units of time are taken to perform the -th step; thus, the first step takes 0.5 units of time, the second takes 0.25, the third 0.125 and so on, so that after one unit of time, a countably infinite number of steps will have been performed.

Infinite time Turing machines

An animation of an infinite time Turing machine based on the Thomson's lamp thought experiment. A cell alternates between
0
{\displaystyle 0}
and
1
{\displaystyle 1}
for steps before
o
{\displaystyle \omega }
. The cell becomes
1
{\displaystyle 1}
at
o
{\displaystyle \omega }
since the sequence does not converge. Animation of Thomson's Lamp Zeno Machine.gif
An animation of an infinite time Turing machine based on the Thomson's lamp thought experiment. A cell alternates between and for steps before . The cell becomes at since the sequence does not converge.

A more formal model of the Zeno machine is the infinite time Turing machine. Defined first in unpublished work by Jeffrey Kidder and expanded upon by Joel Hamkins and Andy Lewis, in Infinite Time Turing Machines, [2] the infinite time Turing machine is an extension of the classical Turing machine model, to include transfinite time; that is time beyond all finite time. [2] A classical Turing machine has a status at step (in the start state, with an empty tape, read head at cell 0) and a procedure for getting from one status to the successive status. In this way the status of a Turing machine is defined for all steps corresponding to a natural number. An ITTM maintains these properties, but also defines the status of the machine at limit ordinals, that is ordinals that are neither nor the successor of any ordinal. The status of a Turing machine consists of 3 parts:

  1. The state
  2. The location of the read-write head
  3. The contents of the tape

Just as a classical Turing machine has a labeled start state, which is the state at the start of a program, an ITTM has a labeled limit state which is the state for the machine at any limit ordinal. [1] This is the case even if the machine has no other way to access this state, for example no node transitions to it. The location of the read-write head is set to zero for at any limit step. [1] [2] Lastly the state of the tape is determined by the limit supremum of previous tape states. For some machine , a cell and, a limit ordinal then

That is the th cell at time is the limit supremum of that same cell as the machine approaches . [1] This can be thought of as the limit if it converges or otherwise. [1]

Computability

Zeno machines have been proposed as a model of computation more powerful than classical Turing machines, based on their ability to solve the halting problem for classical Turing machines. [3] Cristian Calude and Ludwig Staiger present the following pseudocode algorithm as a solution to the halting problem when run on a Zeno machine. [4]

begin program     write 0 on the first position of the output tape;     begin loop         simulate 1 successive step of the given Turing machine on the given input;         if the Turing machine has halted then             write 1 on the first position of the output tape and break out of loop;     end loopend program

By inspecting the first position of the output tape after unit of time has elapsed we can determine whether the given Turing machine halts. [4] In contrast Oron Shagrir argues that the state of a Zeno machine is only defined on the interval , and so it is impossible to inspect the tape at time . Furthermore since classical Turing machines don't have any timing information, the addition of timing information whether accelerating or not does not itself add any computational power. [3]

Infinite time Turing machines however, are capable of implementing the given algorithm, halting at time with the correct solution, [2] since they do define their state for transfinite steps. [3] All sets are decidable by infinite time Turing machines, and sets are semidecidable. [2] [ clarification needed ]

Zeno machines cannot solve their own halting problem. [4]

See also

Related Research Articles

In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.

In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

<span class="mw-page-title-main">Turing machine</span> Computation model defining an abstract machine

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. Despite the model's simplicity, it is capable of implementing any computer algorithm.

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. This is sometimes also formulated as finding the machine that runs for the longest time, but both games are similarly difficult.

<span class="mw-page-title-main">Automata theory</span> Study of abstract machines and automata

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a finite automaton (FA) or finite-state machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.

Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.

In mathematics, limit cardinals are certain cardinal numbers. A cardinal number λ is a weak limit cardinal if λ is neither a successor cardinal nor zero. This means that one cannot "reach" λ from another cardinal by repeated successor operations. These cardinals are sometimes called simply "limit cardinals" when the context is clear.

In set theory, one can define a successor operation on cardinal numbers in a similar way to the successor operation on the ordinal numbers. The cardinal successor coincides with the ordinal successor for finite cardinals, but in the infinite case they diverge because every infinite ordinal and its successor have the same cardinality. Using the von Neumann cardinal assignment and the axiom of choice (AC), this successor operation is easy to define: for a cardinal number κ we have

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions.

P′′ is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines.

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings.

A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank.

A Malament–Hogarth (M-H) spacetime, named after David B. Malament and Mark Hogarth, is a relativistic spacetime that possesses the following property: there exists a worldline and an event p such that all events along are a finite interval in the past of p, but the proper time along is infinite. The event p is known as an M-H event.

A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm.

In computability theory, the mortality problem is a decision problem related to the halting problem. For Turing machines, the halting problem can be stated as follows: Given a Turing machine, and a word, decide whether the machine halts when run on the given word.

In computability theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs.

References

  1. 1 2 3 4 5 Hamkins, Joel (2002-12-03). "Infinite time Turing machines". arXiv: math/0212047 .
  2. 1 2 3 4 5 Hamkins, Joel; Lewis, Andy (1998-08-21). "Infinite Time Turing Machines". arXiv: math/9808093 .
  3. 1 2 3 Shagir, Oron, Super-Tasks, Accelerating Turing Machines and Uncomputability (PDF), archived from the original (PDF) on July 9, 2007
  4. 1 2 3 Calude, Cristian; Staiger, Ludwig, A Note on Accelerated Turing Machines (PDF)