Journal of Computer Technology & Applications

Periodic Turing Machines

  1. Mark Burgin ✉

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 machine

References (24)

  1. Burgin M. Super-recursive Algorithms , Springer, New York/ Heidelberg/ Berlin,.
  2. Burgin M. Nonlinear Phenomena in Spaces of Algorithms, Int J Comp Math 2003; 80(12): 1449–1476p.
  3. Burgin M. Super -recursive Algorithms as a Tool for High Performance Computing , Proceedings of the High Performance Computing Symposium, San Diego, 1999, 224–228p .
  4. Burgin M. Algorithmic Complexity of Recursive and Inductive Algorithms, Theoretical Comp . Sci. 2004; 317(1/3): 31–60p.
  5. Burgin M. Measuring Power of Algorithms, C omputer Programs, and Information Automata, Nova Science Publishers, New York, 2010.
  6. 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.
  7. Burgin M. Algorithmic Complexity of Computational Problems, Int J Comp Infor Tech 2010; 2(1): 149–187p .
  8. 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.
  9. 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.
  10. 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 .
  11. Burgin M., Klinger A. Experience, Generations, and Limits in Machine Learning, Theor Comp Sci 2004; 317(1/3): 71–91p.
  12. 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).
  13. Burgin M., Debnath N., Complexity Measures for Software Engineering , J. Comput Method Sci Eng 2005; 5(1): 127– 143p .
  14. Burgin M., Gupta B. Second-level Algorithms, Superrecursivity, and Recovery Problem in Distributed Systems, Theor Comput Syst 2012; 50(4): 694 – 705p.
  15. Burgin M., Eberbach E. Cooperative Combinatorial Optimization: Evolutionary Computation Case Study, Biosystems 2008; 91(1): 34–50p .
  16. Burgin M., Eberbach E., Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms, Fundamenta Informaticae 2009; 91(1): 53–77p .
  17. 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.
  18. 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
  19. Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory , Languages, and Computation , Addison Wesley, Boston/San Francisco/New York, 2001.
  20. Burgin M. Functioning of Inductive Turing Machines, Int J Unconvent Comp (IJUC) 2014; 10(1-2): 19–35p .
  21. Cook, S.A. and Reckhow, R.A. Time - bounded random access machines, Journal of Computer Systems 1973; 7(4): 354- 375p .
  22. 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 .
  23. Brooker R. Genetics: Analysis and Principles, McGraw -Hill Higher Education, 2011.
  24. Rogers H. Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge, Massachusetts, 1987.

Read more of it

Subscribe to one journal or build your own list of several. One invoice, one payment, access for a full year.

Subscribe to journals →

Publish your article

Peer-reviewed journals across every subject, with open access options. Send your manuscript to the right editor today.

Publish with us → Calculate your APC
Support