The universal Turing machine interpreter

TitleThe universal Turing machine interpreter
Publication TypeJournal Article
Year of Publication2016
AuthorsKurgaev, AF, Grygoryev, SN
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.15407/dopovidi2016.10.028
Issue10
SectionInformation Science and Cybernetics
Pagination28-34
Date Published10/2016
LanguageRussian
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.
Keywordsformal 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