Em 1936, o cientista Alan Turing, em sua publica\u00e7\u00e3o \u201cOn Computable Numbers, With An Application to Entscheidungsproblem\u201d, descreve o uso de uma m\u00e1quina de computa\u00e7\u00e3o universal que poderia p\u00f4r fim ao problema de solubilidade em matem\u00e1tica. Como resultado, ele chega \u00e0 conclus\u00e3o de que tal m\u00e1quina n\u00e3o seria capaz de resolver nada corretamente se o resultado de seu trabalho fosse invertido e girado sobre si mesmo. Acontece que \u00e9 imposs\u00edvel criar um antiv\u00edrus *ideal*, um configurador de blocos *ideal*, um programa que sugira frases ideais para o seu travamento, etc. Paradoxo!<\/p>\n
No entanto, esta m\u00e1quina de computa\u00e7\u00e3o universal pode ser usada para implementar qualquer algoritmo, do qual a intelig\u00eancia brit\u00e2nica se aproveitou, contratando Turing e permitindo a cria\u00e7\u00e3o de uma m\u00e1quina \u201cBombe\u201d para decifrar mensagens alem\u00e3s durante a Segunda Guerra Mundial.<\/p>\n
A seguir est\u00e1 a modelagem OOP de um computador de fita \u00fanica na linguagem Dart, com base no documento original.<\/p>\n
Uma m\u00e1quina de Turing consiste em um filme dividido em se\u00e7\u00f5es, cada se\u00e7\u00e3o cont\u00e9m um s\u00edmbolo, os s\u00edmbolos podem ser lidos ou escritos. Exemplo de aula de cinema:<\/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>\nExiste tamb\u00e9m um \u201cquadrado de digitaliza\u00e7\u00e3o\u201d, que pode mover-se pelo filme, ler ou escrever informa\u00e7\u00f5es, em linguagem moderna – cabe\u00e7a magn\u00e9tica. Exemplo de classe de cabe\u00e7a magn\u00e9tica:<\/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>\nA m\u00e1quina cont\u00e9m \u201cm-configura\u00e7\u00f5es\u201d pelas quais ela pode decidir o que fazer em seguida. Na linguagem moderna – estados e manipuladores de estado. Exemplo de manipulador de estado:<\/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>\nDepois disso, voc\u00ea precisa criar \u201cconfigura\u00e7\u00f5es\u201d, em linguagem moderna s\u00e3o c\u00f3digos de opera\u00e7\u00e3o (opcodes) e seus manipuladores. C\u00f3digos de opera\u00e7\u00e3o de exemplo:<\/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>\nN\u00e3o se esque\u00e7a de criar um opcode e um manipulador de parada, caso contr\u00e1rio voc\u00ea n\u00e3o ser\u00e1 capaz de provar ou deixar\u00e1 de provar (sic!) a resolu\u00e7\u00e3o do problema.<\/strong><\/p>\nAgora, usando o padr\u00e3o \u201cmediador\u201d, conectamos todas as classes da classe Turing Machine, criamos uma inst\u00e2ncia da classe, gravamos o programa atrav\u00e9s de um gravador, carregamos a fita e voc\u00ea pode us\u00e1-la!<\/p >\n
Para mim, pessoalmente, a quest\u00e3o do que era prim\u00e1rio permaneceu interessante – cria\u00e7\u00e3o de uma calculadora universal ou prova do \u201cEntscheidungsproblem\u201d como resultado do qual, como subproduto, apareceu uma calculadora.<\/em><\/p>\nCassetes<\/h3>\n
Para me divertir, gravei v\u00e1rios programas em fita cassete para minha vers\u00e3o da m\u00e1quina.<\/p>\n
Ol\u00e1, mundo<\/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":"Em 1936, o cientista Alan Turing, em sua publica\u00e7\u00e3o \u201cOn Computable Numbers, With An Application to Entscheidungsproblem\u201d, descreve o uso de uma m\u00e1quina de computa\u00e7\u00e3o universal que poderia p\u00f4r fim ao problema de solubilidade em matem\u00e1tica. Como resultado, ele chega \u00e0 conclus\u00e3o de que tal m\u00e1quina n\u00e3o seria capaz de resolver nada corretamente se oContinue reading “Bomba de Turing”<\/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":"pt","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\/pt\/wp-json\/wp\/v2\/posts\/3020","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=3020"}],"version-history":[{"count":17,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3020\/revisions"}],"predecessor-version":[{"id":3893,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3020\/revisions\/3893"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=3020"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=3020"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=3020"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}