The complexity of small universal Turing machines: a survey
---
paper_title: The uniform halting problem for generalized one-state turing machines*

paper_content:

It is shown that the uniform halting problem for one-state Turing machines is solvable. It remains solvable for various generalizations like one-state Turing machines with two-dimensional tape and jumping reading head. Other generalizations, for example, one-state Turing machines with two tapes, have an unsolvable uniform halting problem. The history of the problem is summarized.
---
paper_title: Solvability of the halting problem for certain classes of Turing machines

paper_content:

One method of proving that some Turing machine is not universal is to prove that the halting problem is solvable for it. Therefore, to obtain a lower bound on the complexity of a universal machine, it is convenient to have a criterion of solvability of the halting problem. In the present paper, we establish some of these criteria; they are formulated in terms of properties of machine graphs and computations.
---
paper_title: MINSKY'S SMALL UNIVERSAL TURING MACHINE

paper_content:

Marvin L. Minsky constructed a 4-symbol 7-state universal Turing machine in 1962. It was first announced in a postscript to [2] and is also described in [3, Sec. 14.8]. This paper contains everything that is needed for an understanding of his machine, including a complete description of its operation. Minsky's machine remains one of the minimal known universal Turing machines. That is, there is no known such machine which decreases one parameter without increasing the other. However, Rogozhin [6], [7] has constructed seven universal machines with the following parameters: His 4-symbol 7-state machine is somewhat different from Minsky's, but all of his machines use a construction similar to that used by Minsky. The following corrections should be noted: First machine, for q600Lq1 read q600Lq7; second machine, for q411Rq4 read q411Rq10; last machine, for q2b2bLq2 read . A generalized Turing machine with 4 symbols and 7 states, closely related to Minsky's, was constructed and used in [5].
---
paper_title: A Universal Turing Machine with 3 States and 9 Symbols

paper_content:

With an UTM(3,9) we present a new small universal Turing machine with 3 states and 9 symbols, improving a former result of an UTM(3,10).
---
paper_title: The Nature of Computation

paper_content:

Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. But this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results like interactive proofs, cryptography, and quantum computing are usually considered too "advanced" to show to the typical student. The aim of this book is to bridge both gaps by explaining the deep ideas of theoretical computer science in a clear and enjoyable fashion, making them accessible to non computer scientists and to computer scientists who finally want to understand what their formalisms are actually telling. This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again.
---
paper_title: Decidability and Undecidability of the Halting Problem on Turing Machines, a Survey

paper_content:

The paper surveys the main results obtained for Turing machines about the frontier between a decidable halting problem and universality. The notion of decidability criterion is introduced. Techniques for decidability proofs and for contracting universal objects are sketchily explained. A new approach for finding very small universal Turing machines is considered in the last part of the paper.
---
paper_title: Universality of Tag Systems with P = 2

paper_content:

By a simple direct construction it is shown that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post canonical system with some very strong restrictions. This system is monogenic : each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to the “Tag” variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape nonwriting Turing machines. The proof here avoids these otherwise interesting machines and strengthens the main result; obtaining the theorem with a best possible deletion number P = 2. Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems.
---
paper_title: Surprising Areas in the Quest for Small Universal Devices

paper_content:

In this paper, we study a few points indicated in the talk which we presented at MFCSIT meeting in Cork. Our study concerns three main areas: Turing machines, cellular automata and hyperbolic cellular automata. The common thread is the quest for small universal devices. It leads from properties belonging to the classical domain up to results on super-Turing computations.
---
paper_title: Three Small Universal Turing Machines

paper_content:

We are interested by "small" Universal Turing Machines (in short: UTMs), in the framework of 2, 3 or 4 tape-symbols. In particular: - 2 tape-symbols. Apart from the old 24-states machine constructed by Rogozhin in 1982, we know two recent examples requiring 22 states, one due to Rogozhin and one to the author. - 3 tape-symbols. The best example we know, due to Rogozhin, requires 10 states. It uses a strategy quite hard to follow, in particular because even-length productions require a different treatment with respect to odd-length ones. - 4 tape-symbols. The best known machines require 7 states. Among them, the Rogozhin's one require only 26 commands; the Robinson's one, though requiring 27 commands, fournishes an easier way to recover the output when the TM halts. In particular, Robinson asked for a 7 × 4 UTM with only 26 commands and an easy treatment of the output. ::: ::: Here we will firstly construct a 7 × 4 UTM with an easy recover of the output which requires only 25 commands; then we will simulate such a machine by a (simple) 10 × 3 UT M and by a 19 × 2 UTM.
---
paper_title: Size and structure of universal Turing machines using tag systems

paper_content:

A data transmission system for transmitting information over a plurality of channels or for multiplexing different information on a single channel is described. The system includes a transmitting station where input data signals are linearly transformed into a complementary pulse sequence and transmitted to a receiving station wherein the transmitted pulses are inversely transformed to recover the original signals. The recovered signals are larger in amplitude than the original input signals by a factor dependent on the number of information channels in the system. Any noise introduced during transmission is not made larger in amplitude with the result that the signal to noise ratio of the received signals is improved. The input signals are supplied to a plurality of encoding devices at the transmitter. The encoding devices include tapped delay line devices having multipliers at the taps that multiply the tapped signals by a plus or minus factor in accordance with the code. The multiplied signals are then combined to produce a pulse sequence which is transmitted to the receiving station. At the receiving station the pulse sequence is applied to a plurality of decoding devices. The decoding devices include tapped delay line devices having multipliers at the taps which multiply the tapped signals by a plus or minus factor according to a code which is complementary to the code used at the transmitting station. The multiplied signals are then combined to recover the original input signal which is increased in amplitude by a given factor. The system may be embodied in acoustic surface wave structures wherein the encoding and decoding devices are interdigital transducers.
---
paper_title: On the time complexity of 2-tag systems and small universal Turing machines

paper_content:

We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines.
---
paper_title: Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines

paper_content:

The equivalence of the notions of effective computability as based (1) on formal systems (e.g., those of Post), and (2) on computing machines (e.g., those of Turing) has been shown in a number of ways. The main results of this paper show that the same notions of computability can be realized within (1) the highly restricted monogenic formal systems called by Post the "Tag" systems, and (2) within a peculiarly restricted variant of Turing machine which has two tapes, but can neither write on nor erase these tapes. From these, or rather from the arithmetization device used in their construction, we obtain also an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations. We show first how Turing machines can be regarded as programmed computers. Then by defining a hierarchy of programs which perform certain arithmetic transformations, we obtain the representation in terms of the restricted two-tape machines. These machines, in turn, can be represented in terms of Post normal canonical systems in such a way that each instruction for the machine corresponds to a set of productions in a system which has the monogenic property (for each string in the Post system just one production can operate). This settles the questions raised
---
paper_title: A Universal Turing Machine with 3 States and 9 Symbols

paper_content:

With an UTM(3,9) we present a new small universal Turing machine with 3 states and 9 symbols, improving a former result of an UTM(3,10).
---
paper_title: Small weakly universal Turing machines

paper_content:

We give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines.
---
paper_title: Four small universal Turing machines

paper_content:

We present universal Turing machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbolmachine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universalmachines we present here simulate Turing machines in polynomial time.
---
paper_title: Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality

paper_content:

We define a new criterion which allows to separate cases when all non erasing Turing machines on {0, 1} have a decidable halting problem from cases where a universal non erasing machine can be constructed. It is the case of the number of left instructions in the machine program. In this paper we give the main ideas of the proof for both parts of the frontier result. We prove that there is a universal non-erasing Turing machine whose program has precisely 3 left instructions and that the halting problem is decidable for any non-erasing Turing machine on alphabet {0, 1}, the program of which contains at most 2 left instructions. For this latter result, we have a uniform decision algorithm.
---
paper_title: Small fast universal Turing machines

paper_content:

We present a small time-efficient universal Turing machine with 5 states and 6 symbols. This Turing machine simulates our new variant of tag system. It is the smallest known universal Turing machine that simulates Turing machine computations in polynomial time.
---
paper_title: Splicing systems for universal turing machines

paper_content:

In this paper, we look at extended splicing systems (i.e., H systems) in order to find how small such a system can be in order to generate a recursively enumerable language. It turns out that starting from a Turing machine M with alphabet A and finite set of states Q which generates a given recursively enumerable language L, we need around 2×|I|+2 rules in order to define an extended H system H which generates L, where I is the set of instructions of Turing machine M. Next, coding the states of Q and the non-terminal symbols of L, we obtain an extended H system H 1 which generates L using |A|+2 symbols. At last, by encoding the alphabet, we obtain a splicing system U which generates a universal recursively enumerable set using only two letters.
---
paper_title: On the rule complexity of universal tissue p systems

paper_content:

In the last time several attempts to decrease different complexity parameters (number of membranes, size of rules, number of objects etc.) of universal P systems were done. In this article we consider another parameter which was not investigated yet: the number of rules. We show that 8 rules suffice to recognise any recursively enumerable language if splicing tissue P systems are considered.
---
paper_title: Universality of Tag Systems with P = 2

paper_content:

By a simple direct construction it is shown that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post canonical system with some very strong restrictions. This system is monogenic : each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to the “Tag” variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape nonwriting Turing machines. The proof here avoids these otherwise interesting machines and strengthens the main result; obtaining the theorem with a best possible deletion number P = 2. Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems.
---
paper_title: Some small, multitape universal Turing machines

paper_content:

Abstract The standard way of assigning complexity to a one-tape Turing machine, by the state-symbol product, is clearly inadequate for machines with more than one tape. Letting an (m,n,p)-machine be a Turing machine with m states, n symbols (including any end markers), and p tapes, the number m· n p gives the maximum number of operating rules for an (m,n,p)-machine and serves as a fairly reasonable complexity criterion, reducing to the state-symbol product when p = 1. A (2,3,2)-machine has been designed to simulate an arbitrary tag system with deletion number 2, and therefore is universal [1]. Also a (1,2,4)-machine, having a fixed loop for one of its four tapes, has been designed ; this machine is universal by its ability to simulate an arbitrary “B machine” (6). Under the criterion stated above, these machines have complexities of 18 and 16, respectively, both less than any reported state-symbol product. Moreover, any (m,n,p)-machine may be simulated, step-by-step, by a (1,2,p′)-machine, where p′ = p⌜log 2 (n)⌝ + ⌜log 2 (m)⌝ . If the logarithms are integral, this transformation is realized with no increase in complexity. However, since the full power of the additional tapes is not utilized in this transformation, it appears that this complexity criterion does not provide a severe enough penalty for the introduction of additional tapes to a Turing machine.
---
paper_title: Three Small Universal Turing Machines

paper_content:

We are interested by "small" Universal Turing Machines (in short: UTMs), in the framework of 2, 3 or 4 tape-symbols. In particular: - 2 tape-symbols. Apart from the old 24-states machine constructed by Rogozhin in 1982, we know two recent examples requiring 22 states, one due to Rogozhin and one to the author. - 3 tape-symbols. The best example we know, due to Rogozhin, requires 10 states. It uses a strategy quite hard to follow, in particular because even-length productions require a different treatment with respect to odd-length ones. - 4 tape-symbols. The best known machines require 7 states. Among them, the Rogozhin's one require only 26 commands; the Robinson's one, though requiring 27 commands, fournishes an easier way to recover the output when the TM halts. In particular, Robinson asked for a 7 × 4 UTM with only 26 commands and an easy treatment of the output. ::: ::: Here we will firstly construct a 7 × 4 UTM with an easy recover of the output which requires only 25 commands; then we will simulate such a machine by a (simple) 10 × 3 UT M and by a 19 × 2 UTM.
---
paper_title: Size and structure of universal Turing machines using tag systems

paper_content:

A data transmission system for transmitting information over a plurality of channels or for multiplexing different information on a single channel is described. The system includes a transmitting station where input data signals are linearly transformed into a complementary pulse sequence and transmitted to a receiving station wherein the transmitted pulses are inversely transformed to recover the original signals. The recovered signals are larger in amplitude than the original input signals by a factor dependent on the number of information channels in the system. Any noise introduced during transmission is not made larger in amplitude with the result that the signal to noise ratio of the received signals is improved. The input signals are supplied to a plurality of encoding devices at the transmitter. The encoding devices include tapped delay line devices having multipliers at the taps that multiply the tapped signals by a plus or minus factor in accordance with the code. The multiplied signals are then combined to produce a pulse sequence which is transmitted to the receiving station. At the receiving station the pulse sequence is applied to a plurality of decoding devices. The decoding devices include tapped delay line devices having multipliers at the taps which multiply the tapped signals by a plus or minus factor according to a code which is complementary to the code used at the transmitting station. The multiplied signals are then combined to recover the original input signal which is increased in amplitude by a given factor. The system may be embodied in acoustic surface wave structures wherein the encoding and decoding devices are interdigital transducers.
---
paper_title: A DNA and restriction enzyme implementation of Turing Machines.

paper_content:

Bacteria employ restriction enzymes to cut or restrict DNA ::: at or near specific words in a unique way. Many restriction ::: enzymes cut the two strands of double-stranded DNA at ::: different positions leaving overhangs of single-stranded DNA. Two pieces of DNA may be rejoined or ligated if their ::: terminal overhangs are complementary. Using these operations ::: fragments of DNA, or oligonucleotides, may be inserted and ::: deleted from a circular piece of plasmid DNA. We propose ::: an encoding for the transition table of a Turing machine in ::: DNA oligonucleotides and a corresponding series of restrictions and ligations of those oligonucleotides that, when performed on circular DNA encoding an instantaneous description of a Turing machine, simulate the operation of the Turing machine encoded in those oligonucleotides. DNA based Turing machines have been proposed by Charles Bennett but they invoke imaginary enzymes to perform the state-symbol transitions. Our approach differs in that every operation can be performed using commercially available restriction enzymes and ligases.
---
paper_title: Universal Computation in Simple One-Dimensional Cellular Automata

paper_content:

The existence of computation-universal one-dimensional cellular automata with seven states per cell for a transition function depending on the cell itself and its nearest neighbors (r= 1), and four states per cell for r= 2 (when next-nearest neighbors also are included), is shown. It is also demonstrated that a Turing machine with m tape symbols and n internal states can be simulated by a cellular automaton of range r= 1 with m+ n+ 2 states per cell.
---
paper_title: Small universal Turing machines

paper_content:

Numerous results for simple computationally universal systems are presented, with a particular focus on small universal Turing machines. These results are towards finding the simplest universal systems. We add a new aspect to this area by examining trade-offs between the simplicity of universal systems and their time/space computational complexity. Improving on the earliest results we give the smallest known universal Turing machines that simulate Turing machines in O(t2) time. They are also the smallest known machines where direct simulation of Turing machines is the technique used to establish their universality. This result gives a new algorithm for small universal Turing machines. We show that the problem of predicting t steps of the 1D cellular automaton Rule 110 is P-complete. As a corollary we find that the small weakly universal Turing machines of Cook and others run in polynomial time, an exponential improvement on their previously known simulation time overhead. These results are achieved by improving the cyclic tag system simulation time of Turing machines from exponential to polynomial. A new form of tag system which we call a bi-tag system is introduced. We prove that bi-tag systems are universal by showing they efficiently simulate Turing machines. We also show that 2-tag systems efficiently simulate Turing machines in polynomial time. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves on a forty-year old result. We present new small polynomial time universal Turing machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These machines simulate bi-tag systems and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols, respectively. The 5-symbol machine uses the same number of instructions (22) as the current smallest known universal Turing machine (Rogozhin’s 6-symbol machine). We give the smallest known weakly universal Turing machines. These machines have state-symbol pairs of (6, 2), (3, 3) and (2, 4). The 3-state and 2-state machines are very close to the minimum possible size for weakly universal machines with 3 and 2 states, respectively.
---
paper_title: Book review: A new kind of science

paper_content:

This is a critical review of the book 'A New Kind of Science' by Stephen Wolfram. We do not attempt a chapter-by-chapter evaluation, but instead focus on two areas: computational complexity and fundamental physics. In complexity, we address some of the questions Wolfram raises using standard techniques in theoretical computer science. In physics, we examine Wolfram's proposal for a deterministic model underlying quantum mechanics, with 'long-range threads' to connect entangled particles. We show that this proposal cannot be made compatible with both special relativity and Bell inequality violation.
---
paper_title: Statistical Mechanics of Cellular Automata

paper_content:

Cellular automata are used as simple mathematical models to investigate self-organization in statistical mechanics. A detailed analysis is given of ''elementary'' cellular automata consisting of a sequence of sites with values 0 or 1 on a line, with each site evolving deterministically in discrete time steps according to p definite rules involving the values of its nearest neighbors. With simple initial configurations, the cellular automata either tend to homogeneous states, or generate self-similar patterns with fractal dimensions approx. =1.59 or approx. =1.69. With ''random'' initial configurations, the irreversible character of the cellular automaton evolution leads to several self-organization phenomena. Statistical properties of the structures generated are found to lie in two universality classes, independent of the details of the initial state or the cellular automaton rules. More complicated cellular automata are briefly considered, and connections with dynamical systems theory and the formal theory of computation are discussed.
---
paper_title: A Concrete View of Rule 110 Computation

paper_content:

Rule 110 is a cellular automaton that performs repeated simultaneous updates of an infinite row of binary values. The values are updated in the following way: 0s are changed to 1s at all positions where the value to the right is a 1, while 1s are changed to 0s at all positions where the values to the left and right are both 1. Though trivial to define, the behavior exhibited by Rule 110 is surprisingly intricate, and in (Cook, 2004) we showed that it is capable of emulating the activity of a Turing machine by encoding the Turing machine and its tape into a repeating left pattern, a central pattern, and a repeating right pattern, which Rule 110 then acts on. In this paper we provide an explicit compiler for converting a Turing machine into a Rule 110 initial state, and we present a general approach for proving that such constructions will work as intended. The simulation was originally assumed to require exponential time, but surprising results of Neary and Woods (2006) have shown that in fact, only polynomial time is required. We use the methods of Neary and Woods to exhibit a direct simulation of a Turing machine by a tag system in polynomial time.
---
paper_title: Universality in Elementary Cellular Automata.

paper_content:

The purpose of this paper is to prove that one of the simplest one dimensional cellular automata is computationally universal, implying that many questions concerning its behavior, such as whether a particular sequence of bits will occur, or whether the behavior will become periodic, are formally undecidable. The cellular automaton we will prove this for is known as “Rule 110” according to Wolfram’s numbering scheme [2]. Being a one dimensional cellular automaton, it consists of an infinitely long row of cells "Ci # i $ !%. Each cell is in one of the two states "0, 1%, and at each discrete time step every cell synchronously updates itself according to the value of itself and its nearest neighbors: &i, Ci ( F(Ci)1, Ci, Ci*1), where F is the following function:
---
paper_title: A Particular Universal Cellular Automaton

paper_content:

Signals are a classical tool of cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of colliding signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
---
paper_title: Small weakly universal Turing machines

paper_content:

We give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines.
---
paper_title: Predicting non-linear cellular automata quickly by decomposing them into linear ones

paper_content:

We show that a wide variety of nonlinear cellular automata (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth O(log2 t) using gates with binary inputs, or O(log t) depth if “sum mod p” gates with an unbounded number of inputs are allowed. Thus these CAs can be predicted by (idealized) parallel computers much faster than by explicit simulation, even though they are nonlinear. ::: ::: This class includes any CA whose rule, when written as an algebra, is a solvable group. We also show that CAs based on nilpotent groups can be predicted in depth O(log t) or O(1) by circuits with binary or “sum mod p” gates, respectively. ::: ::: We use these techniques to give an efficient algorithm for a CA rule which, like elementary CA rule 18, has diffusing defects that annihilate in pairs. This can be used to predict the motion of defects in rule 18 in O(log2 t) parallel time.
---
paper_title: The Quest for Small Universal Cellular Automata

paper_content:

We formalize the idea of intrinsically universal cellular automata, which is strictly stronger than classical computational universality. Thanks to this uniform notion, we construct a new one-dimensional universal automaton with von Neumann neighborhood and only 6 states, thus improving the best known lower bound both for computational and intrinsic universality.
---
paper_title: P-completeness of Cellular Automaton Rule 110

paper_content:

We show that. the problem of predicting t steps of the ID cellular automaton Rule 110 is P-complete. The result is found by showing that Rule 110 simulates deterministic Turing machines in polynomial time. As a corollary we find that the small universal Turing machines of Mathew Cook run in polynomial time, this is an exponential improvement on their previously known simulation time overhead.
---
paper_title: Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines

paper_content:

A computation universal Turing machine, U, with 2 states, 4 letters, 1 head and 1 two-dimensional tape is constructed by a translation of a universal register-machine language into networks over some simple abstract automata and, finally, of such networks into U. As there exists no universal Turing machine with 2 states, 2 letters, 1 head and 1 two-dimensional tape only the 2-state, 3-letter case for such machines remains an open problem. An immediate consequence of the construction of U is the existence of a universal 2-state, 2-letter, 2-head, 1 two-dimensional tape Turing machine, giving a first sharp boundary of the necessary complexity of universal Turing machines.
---
paper_title: A simplified universal Turing machine

paper_content:

In 1936 Turing (1) defined a class of logical machines (which he called a - machines, but which are now generally called Turing machines) which he used as an aid in proving certain results in mathematical logic, and which should prove of interest in connection with the theory of control and switching systems. Given any logical operation or arithmetical computation for which complete instructions for carrying out can be supplied, it is possible to design a Turing machine which can perform this operation.
---
paper_title: Some small, multitape universal Turing machines

paper_content:

Abstract The standard way of assigning complexity to a one-tape Turing machine, by the state-symbol product, is clearly inadequate for machines with more than one tape. Letting an (m,n,p)-machine be a Turing machine with m states, n symbols (including any end markers), and p tapes, the number m· n p gives the maximum number of operating rules for an (m,n,p)-machine and serves as a fairly reasonable complexity criterion, reducing to the state-symbol product when p = 1. A (2,3,2)-machine has been designed to simulate an arbitrary tag system with deletion number 2, and therefore is universal [1]. Also a (1,2,4)-machine, having a fixed loop for one of its four tapes, has been designed ; this machine is universal by its ability to simulate an arbitrary “B machine” (6). Under the criterion stated above, these machines have complexities of 18 and 16, respectively, both less than any reported state-symbol product. Moreover, any (m,n,p)-machine may be simulated, step-by-step, by a (1,2,p′)-machine, where p′ = p⌜log 2 (n)⌝ + ⌜log 2 (m)⌝ . If the logarithms are integral, this transformation is realized with no increase in complexity. However, since the full power of the additional tapes is not utilized in this transformation, it appears that this complexity criterion does not provide a severe enough penalty for the introduction of additional tapes to a Turing machine.
---
paper_title: On quasi-unilateral universal Turing machines

paper_content:

Four universal Turing machines are given with strong limitations on the number of left instructions in their program. One of the machines is morever non-erasing, i.e. it does not erase any 1 written on the tape.
---
paper_title: A universal reversible turing machine

paper_content:

A reversible Turing machines is a computing model with a "backward deterministic" property, which is closely related to physical reversibility. In this paper, we study the problem of finding a small universal reversible Turing machine (URTM). As a result, we obtained a 17-state 5-symbol URTM in the quintuple form that can simulate any cyclic tag system.
---
paper_title: Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines

paper_content:

The equivalence of the notions of effective computability as based (1) on formal systems (e.g., those of Post), and (2) on computing machines (e.g., those of Turing) has been shown in a number of ways. The main results of this paper show that the same notions of computability can be realized within (1) the highly restricted monogenic formal systems called by Post the "Tag" systems, and (2) within a peculiarly restricted variant of Turing machine which has two tapes, but can neither write on nor erase these tapes. From these, or rather from the arithmetization device used in their construction, we obtain also an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations. We show first how Turing machines can be regarded as programmed computers. Then by defining a hierarchy of programs which perform certain arithmetic transformations, we obtain the representation in terms of the restricted two-tape machines. These machines, in turn, can be represented in terms of Post normal canonical systems in such a way that each instruction for the machine corresponds to a set of productions in a system which has the monogenic property (for each string in the Post system just one production can operate). This settles the questions raised
---
paper_title: Solvability of the halting problem for certain classes of Turing machines

paper_content:

One method of proving that some Turing machine is not universal is to prove that the halting problem is solvable for it. Therefore, to obtain a lower bound on the complexity of a universal machine, it is convenient to have a criterion of solvability of the halting problem. In the present paper, we establish some of these criteria; they are formulated in terms of properties of machine graphs and computations.
---
paper_title: The laterality problem for non-erasing turing machines on {0,1} is completely solved

paper_content:

In a previous work, [2], we defined a criterion which allowed to separate ceses when all non-erasing Turing machines on {0,1} have a decidable halting problem from cases where a universal non-erasing machine can be constructed. Applying a theorem which entails the just indicated frontier and analogous techniques based upon a qualitative study of the motions of the head of a Turing machine on its tape, another frontier result is here proved, based upon a new criterion, namely the number of left instructions. In this paper, a complete proof of the decidability part of the results is supplied. The case of a single left instruction with a finite alphabet in a generalized non-erasing context is also delt with. Thus, the laterality problem, raised in the early seventies, see [9], solved on {0,1} alphabet without restriction, is now completely solved in the non-erasing case.
---
paper_title: The Solvability of the Halting Problem for 2-State Post Machines

paper_content:

A Post machine is a Turing machine which cannot both write and move on the same machine step. It is shown that the halting problem for the class of 2-state Post machines is solvable. Thus, there can be no universal 2-state Post machine. This is in contrast with the result of Shannon that there exist universal 2-state Turing machines when the machines are capable of both writing and moving on the same step.
---
paper_title: Recursive Unsolvability of a problem of Thue

paper_content:

Alonzo Church suggested to the writer that a certain problem of Thue [6]' might be proved unsolvable by the methods of [5]. We proceed to prove the problem recursively unsolvable, that is, unsolvable in the sense of Church [1], but by a method meeting the special needs of the problem. Thue's (general) problem is the following. Given a finite set of symbols al, a2, ... , a, , we consider arbitrary strings (Zeichenreihen) on those symbols, that is, rows of symbols each of which is in the given set. Null strings are included. We further have given a finite set of pairs of corresponding strings on the ai's, (Al , B1), (A2 , B2), , I (An , B,). A string R is said to be a substring of a string S if S can be written in the form URV, that is, S consists of the letters, in order of occurrence, of some string U, followed by the letters of R, followed by the letters of some string V. Strings P and Q are then said to be similar if Q can be obtained from P by replacing a substring Ai or Bi of P by its correspondent Bi, Ai. Clearly, if P and Q are similar, Q and P are similar. Finally, P and Q are said to be equivalent if there is a finite set R1 , R2, * * *, R, of strings on a,, * * *, a, such that in the sequence of strings P, R1, R2, ... , RX Q each string except the last is similar to the following string. It is readily seen that this relation between strings on a,, * * *, a, ,is indeed an equivalence relation. Thue's problem is then the problem of determining for arbitrarily given strings A, B on al, * * *, a;, whether, or no, A and B are equivalent. This problem, at least for the writer, is more readily placed if it is restated in terms of a special form of the canonical systems of [3]. In that notation, strings C and D are similar if D can be obtained from C by applying to C one of the following operations:
---
paper_title: Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality

paper_content:

We define a new criterion which allows to separate cases when all non erasing Turing machines on {0, 1} have a decidable halting problem from cases where a universal non erasing machine can be constructed. It is the case of the number of left instructions in the machine program. In this paper we give the main ideas of the proof for both parts of the frontier result. We prove that there is a universal non-erasing Turing machine whose program has precisely 3 left instructions and that the halting problem is decidable for any non-erasing Turing machine on alphabet {0, 1}, the program of which contains at most 2 left instructions. For this latter result, we have a uniform decision algorithm.
---
paper_title: Logical reversibility of computation

paper_content:

The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retainillg their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, there by avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), there by restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.
---
paper_title: A simplified universal Turing machine

paper_content:

In 1936 Turing (1) defined a class of logical machines (which he called a - machines, but which are now generally called Turing machines) which he used as an aid in proving certain results in mathematical logic, and which should prove of interest in connection with the theory of control and switching systems. Given any logical operation or arithmetical computation for which complete instructions for carrying out can be supplied, it is possible to design a Turing machine which can perform this operation.
---
paper_title: Counter machines and counter languages

paper_content:

The languages recognizable by time- and space-restricted multiple-counter machines are compared to the languages recognizable by similarly restricted multipletape Turing machines. Special emphasis is placed on languages definable by machines which operate in “real time”. Time and space requirements for counter machines and Turing machines are analyzed. A number of questions which remain open for time-restricted Turing machines are settled for their counter machine counterparts.
---
paper_title: Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines

paper_content:

A computation universal Turing machine, U, with 2 states, 4 letters, 1 head and 1 two-dimensional tape is constructed by a translation of a universal register-machine language into networks over some simple abstract automata and, finally, of such networks into U. As there exists no universal Turing machine with 2 states, 2 letters, 1 head and 1 two-dimensional tape only the 2-state, 3-letter case for such machines remains an open problem. An immediate consequence of the construction of U is the existence of a universal 2-state, 2-letter, 2-head, 1 two-dimensional tape Turing machine, giving a first sharp boundary of the necessary complexity of universal Turing machines.
---
paper_title: Complexity of Langton’s ant

paper_content:

The virtual ant introduced by Langton [Physica D 22 (1986) 120] has an interesting behavior, which has been studied in several contexts. Here we give a construction to calculate any boolean circuit with the trajectory of a single ant. This proves the P-hardness of the system and implies, through the simulation of one-dimensional cellular automata and Turing machines, the universality of the ant and the undecidability of some problems associated to it.
---
paper_title: Studying artificial life with cellular automata

paper_content:

Abstract Biochemistry studies the way in which life emerges from the interaction of inanimate molecules. In this paper we look into the possibility that life could emerge from the interaction of inanimate artificial molecules. Cellular automata provide us with the logical universes within which we can embed artificial molecules in the form of propagating, virtual automata. We suggest that since virtual automata have the computational capacity to fill many of the functional roles played by the primary biomolecules, there is a strong possibility that the ‘molecular logic’ of life can be embedded within cellular automata and that, therefore, artificial life is a distinct possibility within these highly parallel computer structures.
---
paper_title: Three Small Universal Turing Machines

paper_content:

We are interested by "small" Universal Turing Machines (in short: UTMs), in the framework of 2, 3 or 4 tape-symbols. In particular: - 2 tape-symbols. Apart from the old 24-states machine constructed by Rogozhin in 1982, we know two recent examples requiring 22 states, one due to Rogozhin and one to the author. - 3 tape-symbols. The best example we know, due to Rogozhin, requires 10 states. It uses a strategy quite hard to follow, in particular because even-length productions require a different treatment with respect to odd-length ones. - 4 tape-symbols. The best known machines require 7 states. Among them, the Rogozhin's one require only 26 commands; the Robinson's one, though requiring 27 commands, fournishes an easier way to recover the output when the TM halts. In particular, Robinson asked for a 7 × 4 UTM with only 26 commands and an easy treatment of the output. ::: ::: Here we will firstly construct a 7 × 4 UTM with an easy recover of the output which requires only 25 commands; then we will simulate such a machine by a (simple) 10 × 3 UT M and by a 19 × 2 UTM.
---
paper_title: Computation: Finite and Infinite Machines

paper_content:

From the Preface (See Front Matter for full Preface) ::: ::: Man has within a single generation found himself sharing the world with a strange new species: the computers and computer-like machines. Neither history, nor philosophy, nor common sense will tell us how these machines will affect us, for they do not do "work" as did machines of the Industrial Revolution. Instead of dealing with materials or energy, we are told that they handle "control" and "information" and even "intellectual processes." There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and complexity, and that these machines are destined to play important (though not as yet fully understood) roles in society's future. Though only some of us deal directly with computers, all of us are falling under the shadow of their ever-growing sphere of influence, and thus we all need to understand their capabilities and their limitations. ::: ::: It would indeed be reassuring to have a book that categorically and systematically described what all these machines can do and what they cannot do, giving sound theoretical or practical grounds for each judgment. However, although some books have purported to do this, it cannot be done for the following reasons: a) Computer-like devices are utterly unlike anything which science has ever considered---we still lack the tools necessary to fully analyze, synthesize, or even think about them; and b) The methods discovered so far are effective in certain areas, but are developing much too rapidly to allow a useful interpretation and interpolation of results. The abstract theory---as described in this book---tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort. There is no reason to suppose machines have any limitations not shared by man.
---
paper_title: The Busy Beaver Competition: a historical survey

paper_content:

Tibor Rado defined the Busy Beaver Competition in 1962. He used Turing machines to give explicit definitions for some functions that are not computable and grow faster than any computable function. He put forward the problem of computing the values of these functions on numbers 1, 2, 3, ... More and more powerful computers have made possible the computation of lower bounds for these values. In 1988, Brady extended the definitions to functions on two variables. We give a historical survey of these works. The successive record holders in the Busy Beaver Competition are displayed, with their discoverers, the date they were found, and, for some of them, an analysis of their behavior.
---
paper_title: On non-computable functions

paper_content:

The construction of non-computable functions used in this paper is based on the principle that a finite, non-empty set of non-negative integers has a largest element. Also, this principle is used only for sets which are exceptionally well-defined by current standards. No enumeration of computable functions is used, and in this sense the diagonal process is not employed. Thus, it appears that an apparently self-evident principle, of constant use in every area of mathematics, yields non-constructive entities.
---
paper_title: Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines

paper_content:

The equivalence of the notions of effective computability as based (1) on formal systems (e.g., those of Post), and (2) on computing machines (e.g., those of Turing) has been shown in a number of ways. The main results of this paper show that the same notions of computability can be realized within (1) the highly restricted monogenic formal systems called by Post the "Tag" systems, and (2) within a peculiarly restricted variant of Turing machine which has two tapes, but can neither write on nor erase these tapes. From these, or rather from the arithmetization device used in their construction, we obtain also an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations. We show first how Turing machines can be regarded as programmed computers. Then by defining a hierarchy of programs which perform certain arithmetic transformations, we obtain the representation in terms of the restricted two-tape machines. These machines, in turn, can be represented in terms of Post normal canonical systems in such a way that each instruction for the machine corresponds to a set of productions in a system which has the monogenic property (for each string in the Post system just one production can operate). This settles the questions raised
---
paper_title: The Solvability of the Halting Problem for 2-State Post Machines

paper_content:

A Post machine is a Turing machine which cannot both write and move on the same machine step. It is shown that the halting problem for the class of 2-state Post machines is solvable. Thus, there can be no universal 2-state Post machine. This is in contrast with the result of Shannon that there exist universal 2-state Turing machines when the machines are capable of both writing and moving on the same step.
---
paper_title: The Busy Beaver Competition: a historical survey

paper_content:

Tibor Rado defined the Busy Beaver Competition in 1962. He used Turing machines to give explicit definitions for some functions that are not computable and grow faster than any computable function. He put forward the problem of computing the values of these functions on numbers 1, 2, 3, ... More and more powerful computers have made possible the computation of lower bounds for these values. In 1988, Brady extended the definitions to functions on two variables. We give a historical survey of these works. The successive record holders in the Busy Beaver Competition are displayed, with their discoverers, the date they were found, and, for some of them, an analysis of their behavior.
---
paper_title: Limits to Parallel Computation: P-Completeness Theory

paper_content:

This volume provides an ideal introduction to key topics in parallel computing. With its cogent overview of the essentials of the subject as well as lists of P -complete- and open problems, extensive remarks corresponding to each problem, a thorough index, and extensive references, the book will prove invaluable to programmers stuck on problems that are particularly difficult to parallelize. In providing an up-to-date survey of parallel computing research from 1994, Topics in Parallel Computing will prove invaluable to researchers and professionals with an interest in the super computers of the future.
---
paper_title: Busy beaver competition and Collatz-like problems

paper_content:

SummaryThe Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior of the repeated iteration of Collatz-like functions, that is functions defined by cases according to congruence classes.
---
paper_title: Some small, multitape universal Turing machines

paper_content:

Abstract The standard way of assigning complexity to a one-tape Turing machine, by the state-symbol product, is clearly inadequate for machines with more than one tape. Letting an (m,n,p)-machine be a Turing machine with m states, n symbols (including any end markers), and p tapes, the number m· n p gives the maximum number of operating rules for an (m,n,p)-machine and serves as a fairly reasonable complexity criterion, reducing to the state-symbol product when p = 1. A (2,3,2)-machine has been designed to simulate an arbitrary tag system with deletion number 2, and therefore is universal [1]. Also a (1,2,4)-machine, having a fixed loop for one of its four tapes, has been designed ; this machine is universal by its ability to simulate an arbitrary “B machine” (6). Under the criterion stated above, these machines have complexities of 18 and 16, respectively, both less than any reported state-symbol product. Moreover, any (m,n,p)-machine may be simulated, step-by-step, by a (1,2,p′)-machine, where p′ = p⌜log 2 (n)⌝ + ⌜log 2 (m)⌝ . If the logarithms are integral, this transformation is realized with no increase in complexity. However, since the full power of the additional tapes is not utilized in this transformation, it appears that this complexity criterion does not provide a severe enough penalty for the introduction of additional tapes to a Turing machine.
---
paper_title: Frontier between decidability and undecidability: a survey

paper_content:

Abstract After recalling the definition of decidability and universality, we first give a survey of results on the as exact as possible border betweeen a decidable problem and the corresponding undecidablity question in various models of discrete computation: diophantine equations, word problem, Post systems, molecular computations, register machines, neural networks, cellular automata, tiling the plane and Turing machines with planar tape. We then go on with results more specific to classical Turing machines, with a survey of results and a sketchy account on technics. We conclude by an illustration on simulating the 3x+1 problem.
---
paper_title: Study of limits of solvability in tag systems

paper_content:

In this paper we will give an outline of the proof of the solvability of the halting and reachability problem for 2-symbolic tag systems with a deletion number v = 2. This result will be situated in a more general context of research on limits of solvability in tag systems.
---

Title: The Complexity of Small Universal Turing Machines: A Survey

Section 1: Introduction
Description 1: Introduce the topic of small universal Turing machines, including historical context and significant contributions. 

Section 2: Time and Size Efficiency of Universal Machines
Description 2: Discuss the time and program size efficiency of various universal machines, focusing on polynomial time simulators and 2-tag systems.

Section 3: Non-standard Universal Turing Machines: Time Efficiency and Program Size
Description 3: Explore the program size and time complexity results for generalized and restricted models of Turing machines.

Section 4: Weak Universality and Rule 110
Description 4: Cover the concept of weak and semi-weak universality, including the use of repetitive patterns and specific examples like Rule 110.

Section 5: Other Non-standard Universal Turing Machines
Description 5: Present additional generalizations and examples of non-standard universal machines, including those with multiple tapes and multidimensional tapes.

Section 6: Restricted Universal Turing Machines
Description 6: Explain the results for restricted models of Turing machines and their universality, including non-erasing and non-writing Turing machines.

Section 7: Universal Turing Machines with Multidimensional Tapes: Time Efficiency and Program Size
Description 7: Detail the time efficiency and program size results for Turing machines with multidimensional tapes.

Section 8: Termination of a Computation
Description 8: Discuss issues related to the termination of computations in various models of universal Turing machines.

Section 9: Busy Beavers
Description 9: Explore the busy beaver problem and its relationship to small universal Turing machines.

Section 10: Further Work
Description 10: Highlight potential areas for future research in the field of small universal Turing machines.