Title | The universal Turing machine interpreter |
Publication Type | Journal Article |
Year of Publication | 2016 |
Authors | Kurgaev, AF, Grygoryev, SN |
Abbreviated Key Title | Dopov. Nac. akad. nauk Ukr. |
DOI | 10.15407/dopovidi2016.10.028 |
Issue | 10 |
Section | Information Science and Cybernetics |
Pagination | 28-34 |
Date Published | 10/2016 |
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:
- 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