turing machine
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model’s simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm’s logic can be constructed.
One-tape, off-line Turing machine computations
free download
This paper has two purposes. The first is to investigate the characteristics of a restricted class of Turing machines, and to develop a simple tool for describing their computations. The second is to present specific problems for which tight lower bounds can be found for the One of the most important problems in complexity theory is that for separating complexity classes such as A, NA or P(or to prove their coincidence). Recently the following approach proves to be quite successful. One describes the complexity classes under consideration by I became interested in Conways Game of Life in the 1980s when I wrote a Game of Life program for an Amstrad CPC 464. This little computer with 64K of memory ran on a Z80 microprocessor with a 4 MHz clock. The program had a closed universe of 64 128 cells
Palindrome recognition in real time by a multitape Turing machine
free download
Palindromes are sentences that read the same backwards as forwards. Here are a few examples. A man, a plan, a canal, Panama. Dennis and Edna sinned. Red rum, sir, is murder. Live not on evil, madam, live not on evil. Able was I ere 1 saw Elba. Was it a rat I saw
On tape-bounded probabilistic Turing machine acceptors
free download
Atact. A probabilistic Turing machine acecptor is a Turing machine acceptor that flips unbiaseci coins t9 i :: ci 6: what its next move will be and:its input iff the: probability of reaching a finall accep tini, r.: a ;, greater than i. We show that deterministic and probabilistic
Machinic capitalism and network surplus value: Notes on the political economy of the turing machine
free download
Gilbert Simondon once noticed that industrial machines were already information relays, as they were bifurcating for the first time the source of mechanical work (the natural energy) from the source of information (the worker). In 196 in order to describe the new condition of
Universality of Wolframs 3 Turing machine
free download
(This is known as system 0in the proof below.) The proof I intend to give demonstrates that this Turing machine can emulate any two-colour cyclic tag system for an infinite number of steps; in order to do this, I first show that this Turing machine can emulate any two-colour
A Turing machine space hierarchy
free download
This paper introduces a new, finer space complexity measure of computations on Turing machines. The complexity of a computation on a Turing machine now takes into account also the capacity of the finite control. It is proved that a slight enlarging (by an additive
Turing machine simulation by logical neural networks
free download
We naturally extend Aleksanders logical neural networks and show how this extended model simulates the behaviour of a Turing machine . It is widely believed that the only truly neural simulation of a Turing machine should be internal. As a consequence authors have
Deterministic simulation of tape-bounded probabilistic Turing machine transducers
free download
In , it was shown that every language accepted by an S (n) tape-bounded probabilistic Turing machine can be accepted by a deterministic Turing machine within tape O (S (. In this note, we extend this result by showing that S (n) tape-bounded probabilistic machine
Why I am not a super- Turing machine
free download
Page 1. 1 Why I Am Not a Super Turing Machine Gert- C. Lokhorst lokhorst@fwb.eur.nl Faculty of Philosophy Erasmus University Rotterdam UCL, 24 2000 Page 2. PURPOSE 2 Purpose I will discuss the question: Is Man a Super Turing Machine (ie, a machine which is stronger than
Conscious cognition as a discrete, deterministic, and universal Turing Machine process
free download
It is often maintained that the brain-as-computer metaphor is ill taken. Nevertheless one can view conscious cognition as a Turing Machine process, Turing (1937), with its discrete, deterministic, and universal aspects. Not being used to the language of science one may
A Self-Replicating Universal Turing Machine : From von Neumanns Dream to New Embryonic Circuits H ctor Fabio Restrepo, Daniel Mange, and Moshe Sipper
free download
Introduction The Embryonics (embryonic electronics) project is inspired by the basic processes of molecular biology and by the embryonic development of living beings. By adopting three fundamental features of biology multicellular organization, cellular division
After the Turing machine
free download
Problems in implementing DNA and other types of molecular computers stem from the inherent physical nature of molecules and their reactions. The current theory of computation makes assumptions that at best are very crude approximations of the physical chemistry. A
On the notion of universality of Turing machine
free download
Akihiro Nozaki On the notion of universality of Turing machine Persistent URL: http://dml.cz /dmlcz/125257 Institute of Information Theory and Automation AS CR, 1969 Institute of Mathematics of the Academy of Sciences of the Czech Republic provides access to digitized
A Turing machine oracle hierarchy
free download
The paper introduces three complexity measures of computations on Turing machines with oracles. The complexity of a computation on a Turing machine with an oracle is given either by the number of interactions with the oracle during the computation, or by the sum of the
The Turing Machine Revisited
free download
In this paper the authors prove that a conscious machine can exist and specify the conditions that must be satisfied for its existence. Alan Turing demonstrated, in his 1950 paper (Mind 59: 433-460), with calculations, the infeasibility of cognitive machines when
Turing machine task analysis: a method for modelling affordances in the design process
free download
Recently, the affordance-based approach was promoted as an ecological design methodology integrating the user-object interaction dimension. However, the number of properties afforded by an object can potentially be very large. We present a new method
A Universal Turing Machine with Zero Internal States
free download
Can we define the simplest Universal Turing Machine (UTM) as a structure containing only uniform circuits Is there possible a 0-state machine containing only structures having constant sized simple definitions. In a 0-state UTM all random structures are missing, and