The universal Turing machine interpreter

Authors

  • A.F. Kurgaev V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
  • S.N. Grygoryev V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

DOI:

https://doi.org/10.15407/dopovidi2016.10.028

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

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.

Downloads

Download data is not yet available.

References

Glushkov V., Zeitlin G., Yushchenko E. Algebra. Languages. Programming. Kiev, Nauk. Dumka, 1978 (in Russian).

Gross M., Lunten A. Theory of formal grammars. Moscow: Mir, 1971 (in Russian).

Chomsky N. Aspects of the Theory of Syntax, Cambridge, MA: MIT Press, 1965.

Chomsky N. Some Concepts and Consequences of the Theory of Government and Binding, Cambridge, MA: MIT Press, 1982.

International Standard ISO/IEC 14977: 1996(E). Electronic resource. Access: http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf

Kurgaev A., Grygoryev S. Utility model patent UA 92484 U, 2014, Bulletin № 16 (in Ukrainian).

Kurgaev A., Grygoryev S. The normal forms of knowledge. Dopov. Nac. akad. nauk Ukr., 2015, No 11: 36-43 (in Russian).

Fu K.S. Syntactic Pattern Recognition and Applications. Englewood Cliffs: Prentice-Hall, 1982.

Minsky M.L. Computation: Finite and Infinite Machines. Englewood Cliffs: Prentice-Hall, 1967.

Shannon C.E. A universal Turing machine with two internal states. Princeton: Automata Studies, 1956. https://doi.org/10.1515/9781400882618-007

Downloads

Published

23.12.2024

How to Cite

Kurgaev, A., & Grygoryev, S. (2024). The universal Turing machine interpreter . Reports of the National Academy of Sciences of Ukraine, (10), 28–34. https://doi.org/10.15407/dopovidi2016.10.028

Issue

No. 10 (2016): Reports of the National Academy of Sciences of Ukraine

Section

Information Science and Cybernetics

License

Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.