An algorithm to simulate alternating Turing machine in signal machine
Authors:
Preprint
Abstract
Geometrical Computation as a new model of computation is the counterpart of Cellular Automata that has Turing computing ability. In this paper we provide an algorithm to simulate Alternating Turing Machine in the context of Signal Machine using techniques adopted from the features of Signal Machine to set up and manage the copies/branches of Alternating Turing Machine. We show that our algorithm can simulate Alternating Turing Machine in Signal Machine as same functionality as classic family of Turing Machines. Time complexity of the algorithm is linear as ordinary simulated Turing Machines. Depending on the computation tree space complexity is exponential order of d, where d is the depth of the computation tree.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Abstract geometrical computation 8: Small machines, accumulations & rationalityJournal of Computer and System Sciences, 2018
- Abstract geometrical computation 7: geometrical accumulations and computably enumerable real numbersNatural Computing, 2012
- Abstract geometrical computation 4: Small Turing universal signal machinesTheoretical Computer Science, 2011
- Abstract geometrical computation 5: embedding computable analysisNatural Computing, 2010
- Abstract geometrical computation 3: black holes for classical and analog computingNatural Computing, 2009
- Small deterministic Turing machinesTheoretical Computer Science, 1996