Journal of Computer Technology & Applications
Periodic Turing Machines
Abstract
AbstractIt is proved that in comparison with Turing machines, inductive Turing machines represent the next step in the development of computer science providing better models for contemporary computers and computer networks. In particular, it is proved that simple inductive Turing machines can solve the Halting Problem for Turing machines, while inductive Turing machines of higher orders can generate and decide the whole arithmetical hierarchy. It means that inductive Turing machines are super-recursive algorithms, which model and perform unconventional computations. Inductive Turing machines are a particular case of periodic Turing machines. Thus, periodic Turing machines are super-recursive algorithms, which are more powerful than Turing machines. At the same time, periodic Turing machines reflect pivotal traits of periodic computational processes. In this paper, we study relations between periodic and inductive Turing machines.Keywords: Computation, stability, turing machine, inductive Turing machine, periodic turing machineReferences (24)
- Burgin M. Super-recursive Algorithms , Springer, New York/ Heidelberg/ Berlin,.
- Burgin M. Nonlinear Phenomena in Spaces of Algorithms, Int J Comp Math 2003; 80(12): 1449–1476p.
- Burgin M. Super -recursive Algorithms as a Tool for High Performance Computing , Proceedings of the High Performance Computing Symposium, San Diego, 1999, 224–228p .
- Burgin M. Algorithmic Complexity of Recursive and Inductive Algorithms, Theoretical Comp . Sci. 2004; 317(1/3): 31–60p.
- Burgin M. Measuring Power of Algorithms, C omputer Programs, and Information Automata, Nova Science Publishers, New York, 2010.
- Burgin M., Algorithmic Control in Concurrent Computations, in Proceedings of the 2006 International Conference on Foundations of Computer Science , CSREA Press, Las Vegas, June, 2006, 17– 23p.
- Burgin M. Algorithmic Complexity of Computational Problems, Int J Comp Infor Tech 2010; 2(1): 149–187p .
- a) Burgin M., Calude C.S., Calude E. Inductive Complexity Measures for Mathematical Problems, Int J Found Comp Sci 2013; 24(4): 487–500p. b) Burgin M. Algorithmic Complexity as a criterion of unsolvability, Theoretical Comp Sci 2007; 383(2/3): 244–259p.
- Burgin M., Debnath N., Super-Recursive Algorithms in Testing Distributed Systems, in Proceedings of the ISCA 24 th International Conference “Computers and their Applications” (CATA -2009), ISCA, New Orleans, Louisiana, USA, April, 2009, 209–214p.
- Burgin M., Debnath N., Lee H. K., Measuring Testing as a Distributed Component of the Software Life Cycle , J Comput Method Sci Eng 2009; 9(1/ 2, 2): 211–223p .
- Burgin M., Klinger A. Experience, Generations, and Limits in Machine Learning, Theor Comp Sci 2004; 317(1/3): 71–91p.
- Burgin M., Debnath N., Measuring Software Maintenance, in Proceedings of the ISCA 19 th International Conference “Computers and their Applications” , ISCA, Seattle, Washington, 2004, 118 – 121p. (in collaboration).
- Burgin M., Debnath N., Complexity Measures for Software Engineering , J. Comput Method Sci Eng 2005; 5(1): 127– 143p .
- Burgin M., Gupta B. Second-level Algorithms, Superrecursivity, and Recovery Problem in Distributed Systems, Theor Comput Syst 2012; 50(4): 694 – 705p.
- Burgin M., Eberbach E. Cooperative Combinatorial Optimization: Evolutionary Computation Case Study, Biosystems 2008; 91(1): 34–50p .
- Burgin M., Eberbach E., Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms, Fundamenta Informaticae 2009; 91(1): 53–77p .
- Burgin M., Eberbach E., On Foundations of Evolutionary Computation: An Evolutionary Automata Approach, in Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies , IGI Global, Hershey, Pennsylvania, 2009a, 342–360p.
- Burgin M. Superrecursive Hierarchies of Algorithmic P roblems, in Proceedings of the 2005 International Conference on Foundations of Computer Science , CSREA Press, Las Vegas, June, 2005, 31– 37p . Journal of Computer Technology & Applications Volume 5, Issue 3 ISSN: 2229-6964 (online), ISSN: 2347-7229 (print) JoCTA (2014) 6-18 © STM Journals 2014. All Rights Reserved Page 18
- Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory , Languages, and Computation , Addison Wesley, Boston/San Francisco/New York, 2001.
- Burgin M. Functioning of Inductive Turing Machines, Int J Unconvent Comp (IJUC) 2014; 10(1-2): 19–35p .
- Cook, S.A. and Reckhow, R.A. Time - bounded random access machines, Journal of Computer Systems 1973; 7(4): 354- 375p .
- Deutsch, D. Quantum theory, the Church - Turing principle and the universal quantum computer, Proceedings of the Royal Society of London 1985, A 400: 97- 117p .
- Brooker R. Genetics: Analysis and Principles, McGraw -Hill Higher Education, 2011.
- Rogers H. Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge, Massachusetts, 1987.