Results 181 to 190 of about 50,371 (207)

The CNN is universal as the Turing machine

IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 1993
It is shown that the game of life algorithm, which is equivalent to a Turing machine, can be realized by a cellular neural network (CNN). Thus the CNN is also universal. >
Tamás Roska, Leon O. Chua, P.L. Venetianer   +2 more
openaire   +2 more sources

Beyond the universal Turing machine

Australasian Journal of Philosophy, 1999
(1999). Beyond the universal Turing machine. Australasian Journal of Philosophy: Vol. 77, No. 1, pp. 46-66.
B. Jack Copeland, Richard Sylvan
openaire   +2 more sources

Turing’s Thesis and the Universality of the Turing Machine

2002
In this chapter, we investigate Turing’s thesis, which essentially says that the Turing machine (TM) is the most powerful computational device of all. We find evidence to support the thesis by considering a special TM called the Universal TM (UTM).
openaire   +2 more sources

Note on a universal quantum Turing machine

Physics Letters A, 2008
In this Letter, we construct a novel model of universal quantum Turing machine (QTM) by means of a property of Riemann zeta function, which is free from the specific time for an input data and efficiently simulates each step of a given QTM.
Takayuki Miyadera, Masanori Ohya, Satoshi Iriyama   +2 more
openaire   +2 more sources

A Universal Reversible Turing Machine

2007
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.
Kenichi Morita, Yoshikazu Yamaguchi
openaire   +2 more sources

A simplified universal Turing machine

Proceedings of the 1952 ACM national meeting (Toronto) on - ACM '52, 1952
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
openaire   +2 more sources

On reversible Turing machines and their function universality

Acta Informatica, 2016
We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function $$\lambda x.f(x)$$źx.f(x) and computing the function $$\lambda x. (x, f(x))$$źx.(x,f(x)), or other injective embeddings of f.
Holger Bock Axelsen, Robert Glück
openaire   +3 more sources

The Complexity of Small Universal Turing Machines

2007
We survey some work concerned with small universal Turing machines, cellular automata, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are
Turlough Neary, Damien Woods
openaire   +2 more sources

Universal Counter Machine—Turing Machine

2015
Paul Chapman’s universal counter machine described in Chap. 3 is universal because it can simulate an arbitrary counter machine. It has been shown by Minsky that a counter machine can also simulate an arbitrary Turing machine. This chapter describes such a machine implemented by the author in Conway’s Game of Life and compares this with Paul Chapman’s ...
openaire   +2 more sources

A Simple Universal Turing Machine for the Game of Life Turing Machine

2010
In this chapter we present a simple universal Turing machine which is small enough to fit into the design limits of the Turing machine build in Conway’s Game of Life by the author. That limit is 8 symbols and 16 states. By way of comparison we also describe one of the smallest known universal Turing machines due to Rogozhin which has 6 symbols and 4 ...
openaire   +2 more sources