Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 17 of 17 for “"turing machine"”.
-
A relatively small turing machine whose behavior is independent of set theory
… an explicit description of a 340,943-state Turing machine Z with 1 tape and a 2-symbol alphabet whose behavior cannot be proved in ZFC, assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. Ill In doing so, I …
-
On a Reducibility Concept Among Sets of Infinite Strings Induced by Turing Machine Transducers
Made available in DSpace on 2014-12-11T18:24:11Z (GMT). No. of bitstreams: 1 7500301.pdf: 1963619 bytes, checksum: cf36fe9cedab4965903d68950b525d13 (MD5) Previous issue date: 1974
-
Extended cognition, dynamics, and algorithms. A turing machine based approach to the study of arithmetical skills
… activities is explicitely recognized in Alan Turing's theory of computation, which is focused on the construction of idealized models of the mechanisms at work in a real cognitive system, namely the one consisting of a man performing calculations with paper and pencil. In the present thesis I …
-
The power of parallel time
… we address the following question: Are parallel machines always faster than sequential machines? Our approach is to examine the common machine models of sequential computation. For each such machine ${\cal M}$ that runs in time T, we determine whether it is possible to speed up ${\cal M}$ by a …
-
Computational complexity of random-access models
… models is considered. These models are the Turing machine and its multidimensional variant, the random access machine (RAM), the tree machine, and the pointer machine. The basic computational properties of the pointer machine are examined in more detail. For example, time and space hierarchy …
-
DAN-based string rewrite computational systems
… showing how Minsky's 4-symbol 7-state Universal Turing Machine can be implemented using a programmed mutagenesis system. Each step of the Universal Turing Machine is implemented by four cycles of programmed mutagenesis, and progress is guaranteed by the use of alternate sense strands for each …
-
Automata on Cayley Graphs
… of the ordinary doubly infinite tape of a Turing machine are hidden behind the contents of the symbols written on it. An observer standing on a blank tape will be unable to distinguish one cell from another on the sole basis of their local appearance or relative position: the tape is …
-
Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
… that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration C' in T+1 steps. It is unambiguous meaning that it is hard to produce two different …
-
A transdisciplinary study of embodiment in HCI, AI and New Media.
… thinking about human embodiment in relation to machine embodiment. A practical dimension of this thesis is to elicit some principles for the design and evaluation of virtual embodiment. The transdisciplinary approach suggests, firstly, that a single discipline or reality is, on its own, not …
-
Transitive Closure Logic and Multihead Automata with Nested Pebbles
… that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities …
-
Turing-Completeness as Medium: Art, Computers and Intentionality
… media device or some sort of “multimedia” machine. These terms leave the existence of a specific computing medium in art practice undefined and have historically led the analysis of artworks that employ computers to rely on critical frameworks that were either developed for earlier physical …
-
Quantum Stochastic Processes and Quantum Many-Body Physics
… study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
-
Out of Equilibrium: Modelling and Simulating Traverse
… non ad-hoc, manner. We model innovations using Turing Machine metaphor, so that we can encapsulate the intrinsic uncertainties of Research and Development processes in an insightful way. The enhanced ‘time-to-build’ model thus developed is then simulated for various policy parameters, such as - …
-
Computational methods for multi-omic models of cell metabolism and their importance for theoretical computer science
… executes reactions mapped to instructions of a Turing machine. A Boolean string represents the genetic knockout strategy and also the executable program stored in the “memory” of the organism. I use this framework to investigate scenarios of communication among cells, gene duplication, and …
-
The Foundations of Infinite-Dimensional Spectral Computations
… led to a real-number counterpart of the Turing machine, yet left a substantial gap between theory and practice. The SCI hierarchy encompasses both these models and provides universal bounds on what is computationally possible. What makes spectral problems particularly delicate is that …
-
Addressing nonlinear systems with information-theoretical techniques
… given an input sequence and a universal Turing machine, Kolmogorov found that the length of the shortest set of instructions, i.e. the program, that enables the machine to compute the input sequence was related to the sequence’s entropy. This definition of the complexity of a sequence …