Small universal Turing machines
Y Rogozhin - Theoretical Computer Science, 1996 - Elsevier
Small universal Turing machines Page 1 ELSEVIER Theoretical Computer Science 168 (1996)
2 1 S-240 Theoretical Computer Science Small universal Turing machines Yurii Rogozhin …
2 1 S-240 Theoretical Computer Science Small universal Turing machines Yurii Rogozhin …
Small universal register machines
I Korec - Theoretical Computer Science, 1996 - Elsevier
Several small universal register machines are constructed. The number of instructions vary
from 32 to 14, depending on the chosen instruction base and the chosen notion of …
from 32 to 14, depending on the chosen instruction base and the chosen notion of …
Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
Page 1 ELSEVIER Theoretical Computer Science 210 (1999) 217-223 Theoretical Computer …
Page 1 ELSEVIER Theoretical Computer Science 210 (1999) 217-223 Theoretical Computer …
Tag systems and Collatz-like functions
L De Mol - Theoretical Computer Science, 2008 - Elsevier
Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin
Minsky. These production systems have proved to be very useful in constructing small …
Minsky. These production systems have proved to be very useful in constructing small …
Three small universal Turing machines
C Baiocchi - … , and Universality: Third International Conference, MCU …, 2001 - Springer
We are interested by “small” Universal Turing Machines (in short: UTMs), in the framework of
2, 3 or 4 tape—symbols. In particular: tape—symbols. Apart from the old 24—states machine …
2, 3 or 4 tape—symbols. In particular: tape—symbols. Apart from the old 24—states machine …
A universal Turing machine with 3 states and 9 symbols
M Kudlek, Y Rogozhin - … in Language Theory: 5th International Conference …, 2002 - Springer
A Universal Turing Machine with 3 States and 9 Symbols Page 1 A Universal Turing Machine with
3 States and 9 Symbols Manfred Kudlek 1 and Yurii Rogozhin 2 1 Fachbereich Informatik …
3 States and 9 Symbols Manfred Kudlek 1 and Yurii Rogozhin 2 1 Fachbereich Informatik …
[PDF][PDF] Finite-dimensional analog computers: Flows, maps, and recurrent neural networks
C Moore - 1st International Conference on …, 1998 - languagelog.ldc.upenn.edu
A number of authors have explored the computational power of dynamical systems with a
finite number of continuous degrees of freedom. We review this work, from the point of view …
finite number of continuous degrees of freedom. We review this work, from the point of view …
Busy beaver competition and Collatz-like problems
P Michel - Archive for Mathematical Logic, 1993 - Springer
Summary The 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 …
taking much time or leaving many marks, when starting from a blank tape. In order to …
Small Turing machines and generalized busy beaver competition
P Michel - Theoretical Computer Science, 2004 - Elsevier
Let TM (k, l) be the set of one-tape Turing machines with k states and l symbols. It is known
that the halting problem is decidable for machines in TM (2, 3) and TM (3, 2). We prove that …
that the halting problem is decidable for machines in TM (2, 3) and TM (3, 2). We prove that …
Minsky's small universal Turing machine
RM Robinson - International Journal of Mathematics, 1991 - World Scientific
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 …
first announced in a postscript to [2] and is also described in [3, Sec. 14.8]. This paper …