The universal Turing machine interpreter

1Kurgaev, AF, 1Grygoryev, SN
1V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2016, 10:28-34
https://doi.org/10.15407/dopovidi2016.10.028
Section: Information Science and Cybernetics
Language: Russian
Abstract: 

Using an interpreter of the universal Turing machine as the example, it is shown that the NFK (normal forms of knowledge) meta-language expressiveness is sufficient for defining and solving any solvable problem, which proves the versatility of a computer, which realizes this language. In the process of substantiation of the versatility of the NFK meta-language, the formal text and graphical descriptions of an interpreter of the universal Turing machine are given.

Keywords: formal language, interpretative and translating process of statement and solution of problems, interpreter of the universal Turing machine, knowledge base, meta-language of normal forms of knowledge
References: 
  1. Glushkov V., Zeitlin G., Yushchenko E. Algebra. Languages. Programming. Kiev, Nauk. Dumka, 1978 (in Russian).
  2. Gross M., Lunten A. Theory of formal grammars. Moscow: Mir, 1971 (in Russian).
  3. Chomsky N. Aspects of the Theory of Syntax, Cambridge, MA: MIT Press, 1965.
  4. Chomsky N. Some Concepts and Consequences of the Theory of Government and Binding, Cambridge, MA: MIT Press, 1982.
  5. International Standard ISO/IEC 14977: 1996(E). Electronic resource. Access: http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
  6. Kurgaev A., Grygoryev S. Utility model patent UA 92484 U, 2014, Bulletin № 16 (in Ukrainian).
  7. Kurgaev A., Grygoryev S. The normal forms of knowledge. Dopov. Nac. akad. nauk Ukr., 2015, No 11: 36-43 (in Russian).
  8. Fu K.S. Syntactic Pattern Recognition and Applications. Englewood Cliffs: Prentice-Hall, 1982.
  9. Minsky M.L. Computation: Finite and Infinite Machines. Englewood Cliffs: Prentice-Hall, 1967.
  10. Shannon C.E. A universal Turing machine with two internal states. Princeton: Automata Studies, 1956. https://doi.org/10.1515/9781400882618-007