Journal of Computer Technology & Applications

Inductively Computable Sets and Functions

  1. Mark Burgin ✉

Abstract

AbstractInductive computations are used in many areas of computer and network technology. Inductive reasoning forms the base for scientific exploration. A mathematical model of inductive computations and reasoning is called an inductive Turing machine, which is a natural extension of the most popular model of computing devices and computations - Turing machine. 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. Inductive Turing machines generate inductively computable sets, separate inductively recognizable sets, discern inductively decidable sets and compute inductively computable functions. In this paper, we study properties of these sets and functions.Keywords: Inductive computation, Turing machine, Inductive Turing machine, Inductive computability, Inductive recognizability, Inductive decidabilityCite this ArticleMark Burgin. Inductively Computable Sets and Functions. Journal of Computer Technology & Applications. 2016; 7(1): 12–21p.

References (21)

  1. Burgin M. Super-recursive Algorithms , Springer, New York/ Heidelberg/ Berlin, 2005.
  2. Burgin M. Algorithmic Complexity of Recursive and Inductive Algorithms, Theor Comput Sci . 2004; 317(1/3): 31 – 60p.
  3. Burgin M. Algorithmic Complexity of Computational Problems, Int J Comput Inform Technol. 2010; 2(1): 149–187p.
  4. 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.
  5. Burgin M, Debnath N, Lee HK. Measuring Testing as a Distributed Component of the Software Life Cycle , J Comput Method Sci Eng. 2009; 9(1/2), 2: 211–223p.
  6. Burgin M. Super -recursive Algori thms as a Tool for High Performance Computing, in Proceedings of the High Performance Computing Symposium, San Diego, 1999, 224–228p.
  7. Burgin M, Klinger A. Experience, Generations, and Limits in Machine Learning, Theor Comput Sci . 2004; 317(1/3): 71–91p. Inductively Computable Sets and Functions Burgin Mark JoCTA (2016) 12-21 © STM Journals 2016. All Rights Reserved Page 21
  8. 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.
  9. Burgin M, Debnath N. Complexity Measures for Software Engineering, J Comput Method Sci Eng. 2005; 5(1): 127– 143p.
  10. 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.
  11. Burgin M, Gupta B. Second-level Algorithms, Super recursivity, and Recovery Problem in Distributed Systems, Theor Comput Syst . 2012; 50(4): 694–705p.
  12. Burgin M, Eberbach E, Universality for Turing Machines, Inductive Turing Machines and Evoluti onary Algorithms, Fundment Informaticae, 2009; 91(1): 53– 77p.
  13. 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 C omplex Adaptive Technologies (Hongwei Mo, Ed.), IGI Global, Hershey, Pennsylvania, 2009, 342–360p.
  14. Burgin M, Eberbach E. Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation, Comput J . 2012; 55(9): 1023–1029p.
  15. Beros AA. Learning Theory in the Arithmetical Hierarchy, J Symbolic Logic. September 2014; 79(03): 908 –927p. Preprint in mathematics, math. LO/1302.7069, 2013 (electronic edition: http://arXiv.org)
  16. Gold EM. Language Identification in the Limit, Inform Control . 1967; 10: 447 – 474p.
  17. Calinescu R, France R, Ghezzi C. Editorial, Computing. 2013; 95(3): 165 – 166p.
  18. Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory , Languages, and Computation , Addison Wesley, Boston/San Francisco/New York, 2007.
  19. Li M, Vitan yi P. An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1997.
  20. Burgin M. Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, 1983; 270(6): 1289–1293p. (translated from Russian, v. 27, No. 3)
  21. Burgin M. Measuring Power of Algorithms, Computer Programs, and Information Automata, Nova Science Publishers, New York, 2010. Cite this Article Mark Burgin. Inductively Computable Sets and Functions. Journal of Computer Technology & Appl ications. 2016; 7(1): 12–21p.

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