In 1936, scientist Alan Turing in his publication “On Computable Numbers, With An Application to Entscheidungsproblem” describes the use of a universal computing machine that could put an end to the question of the solvability problem in mathematics. As a result, he comes to the conclusion that such a machine would not be able to solve anything correctly if the result of its work was inverted and looped back to itself. It turns out that it is impossible to create an *ideal* antivirus, an *ideal* tile layer, a program that suggests ideal phrases for your crash, etc. Paradox!<\/p>\n
However, this universal computing machine can be used to implement any algorithm, which is what British intelligence took advantage of by hiring Turing and allowing him to create the \u201cBombe\u201d machine to decipher German messages during World War II.<\/p>\n
The following is an OOP simulation of a single-tape computer in Dart, based on the original document.<\/p>\n
A Turing machine consists of a film divided into sections, each section contains a symbol, the symbols can be read or written. An example of a film class:<\/p>\n
final _map = Map<int, String>(); \n\n String read({required int at}) { \n return _map[at] ?? \"\"; \n } \n\n void write({required String symbol, required int at}) { \n _map[at] = symbol; \n } \n}\n<\/code><\/pre>\n<\/div>\nThere is also a \u201cscanning square\u201d, it can move along the film, read or write information, in modern language – a magnetic head. An example of a magnetic head class:<\/p>\n
\n int _index = 0; \n InfiniteTape _infiniteTape; \n TapeHead(this._infiniteTape) {} \n\n String next() { \n _index += 1; \n move(to: _index); \n final output = read(); \n return output; \n } \n\n String previous() { \n _index -= 1; \n move(to: _index); \n final output = read(); \n return output; \n } \n\n void move({required int to}) { \n this._index = to; \n } \n\n String read() { \n return _infiniteTape.read(at: this._index); \n } \n\n void write(String symbol) { \n _infiniteTape.write(symbol: symbol, at: this._index); \n } \n\n int index() { \n return _index; \n } \n} \n<\/code><\/pre>\n<\/div>\nThe machine contains \u201cm-configurations\u201d by which it can decide what to do next. In modern language, these are states and state handlers. An example of a state handler:<\/p>\n
\n FiniteStateControlDelegate? delegate = null; \n\n void handle({required String symbol}) { \n if (symbol == OPCODE_PRINT) { \n final argument = delegate?.nextSymbol(); \n print(argument);\n } \n else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) { \n final to = int.tryParse(delegate!.nextSymbol())!; \n final value = new Random().nextInt(to); \n delegate!.nextSymbol(); \n delegate!.write(value.toString()); \n } \n else if (symbol == OPCODE_INPUT_TO_NEXT) { \n final input = stdin.readLineSync()!; \n delegate?.nextSymbol(); \n delegate?.write(input); \n } \n else if (symbol == OPCODE_COPY_FROM_TO) { \n final currentIndex = delegate!.index(); \n\n\u0438 \u0442.\u0434. \n<\/code><\/pre>\n<\/div>\nAfter this, you need to create \u201cconfigurations\u201d, in modern language these are operation codes (opcodes), their handlers. An example of opcodes:<\/p>\n
\nconst OPCODE_PRINT = \"print\"; \nconst OPCODE_INCREMENT_NEXT = \"increment next\"; \nconst OPCODE_DECREMENT_NEXT = \"decrement next\"; \nconst OPCODE_IF_PREVIOUS_NOT_EQUAL = \"if previous not equal\"; \nconst OPCODE_MOVE_TO_INDEX = \"move to index\"; \nconst OPCODE_COPY_FROM_TO = \"copy from index to index\"; \nconst OPCODE_INPUT_TO_NEXT = \"input to next\"; \nconst OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = \"generate random number from zero to next and write after\"; \n<\/code><\/pre>\n<\/div>\nDon’t forget to create an opcode and a stop handler, otherwise you won’t be able to prove or not prove (sic!) the resolution problem.<\/strong><\/p>\nNow, using the \u201cmediator\u201d pattern, we connect all the classes in the Turing Machine class, create an instance of the class, record the programs on tape using a tape recorder, load the tape and you can use it!<\/p>\n
For me personally, the question of what came first remains interesting: the creation of a universal computer or the proof of the \u201cEntscheidungsproblem\u201d, which resulted in the computer appearing as a by-product.<\/em><\/p>\nCassettes<\/h3>\n
For fun, I recorded several cassette programs for my version of the machine.<\/p>\n
Hello World<\/strong><\/p>\n\nhello world \nstop<\/code><\/pre>\n\u0421\u0447\u0438\u0442\u0430\u0435\u043c \u0434\u043e 16-\u0442\u0438<\/strong><\/p>\n\n0\nif previous not equal\n16\ncopy from index to index\n1\n8\nprint\n?\nmove to index\n0\nelse\ncopy from index to index\n1\n16\nprint\n?\nprint\nFinished!\nstop<\/code><\/pre>\n\u0421\u0430\u043c\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0431\u044b\u043b\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0435 Quine \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0435\u0447\u0430\u0442\u0430\u0435\u0442 \u0441\u0432\u043e\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434, \u0434\u043b\u044f \u043e\u0434\u043d\u043e\u043b\u0435\u043d\u0442\u043e\u0447\u043d\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u044b. \u041f\u0435\u0440\u0432\u044b\u0435 8 \u0447\u0430\u0441\u043e\u0432 \u043c\u043d\u0435 \u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0447\u0442\u043e \u044d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0435 \u0440\u0435\u0448\u0430\u0435\u043c\u0430 \u0441 \u0442\u0430\u043a\u0438\u043c \u043c\u0430\u043b\u044b\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u043e\u043f\u043a\u043e\u0434\u043e\u0432, \u043e\u0434\u043d\u0430\u043a\u043e \u0432\u0441\u0435\u0433\u043e \u0447\u0435\u0440\u0435\u0437 16 \u0447\u0430\u0441\u043e\u0432 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0447\u0442\u043e \u044f \u0431\u044b\u043b \u043d\u0435 \u043f\u0440\u0430\u0432.<\/p>\n
\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u043a\u0430\u0441\u0441\u0435\u0442, \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438 \u043d\u0438\u0436\u0435.<\/p>\n
\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n
https:\/\/gitlab.com\/demensdeum\/turing-machine<\/a><\/p>\n\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h3>\n
https:\/\/www.astro.puc.cl\/~rparra\/tools\/PAPERS\/turing_1936.pdf<\/a>
\nhttps:\/\/kpolyakov.spb.ru\/prog\/turing.htm<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=dNRDvLACg5Q<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=jP3ceURvIYc<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=9QCJj5QzETI<\/a>
\nhttps:\/\/www.youtube.com\/watch?v=HeQX2HjkcNo&t=0s<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"In 1936, scientist Alan Turing in his publication “On Computable Numbers, With An Application to Entscheidungsproblem” describes the use of a universal computing machine that could put an end to the question of the solvability problem in mathematics. As a result, he comes to the conclusion that such a machine would not be able toContinue reading “Turing Bomb”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[178,175,177,176],"class_list":["post-3020","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-abstract","tag-computer-science","tag-machine","tag-turing","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"hi","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3020","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/comments?post=3020"}],"version-history":[{"count":17,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3020\/revisions"}],"predecessor-version":[{"id":3893,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3020\/revisions\/3893"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/media?parent=3020"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/categories?post=3020"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/tags?post=3020"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}