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
Section: Information Science and Cybernetics
Language: Russian

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
  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:
  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.