In 1936, the 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 problem of decidability in mathematics. As a result, he comes to the conclusion that such a machine would be nothing could solve correctly, if the result of her work would be inverted and looped on itself.It turns out that * ideal * antivirus cannot be created, * ideal * tile layer too, a program that suggests ideal phrases for your crash, etc. Paradox, sir!
However, this universal computing machine can be used to implement any algorithm, which was used by British intelligence, hiring Turing and allowing to create a “Bombe” machine for decrypting German messages during the Second World War.
The following is an example of OOP modeling a single-tape calculator in Dart, based on the original document.
The Turing machine consists of a tape divided into sections, each section contains a symbol, symbols can be read or written. Film class example:
class MapInfiniteTape implements InfiniteTape {
final _map = Map<int, String>();
String read({required int at}) {
return _map[at] ?? "";
}
void write({required String symbol, required int at}) {
_map[at] = symbol;
}
}
There is also a “scanning square”, it can move along the film, read or write information, in modern language – a magnetic head. Magnetic head class example:
class TapeHead {
int _index = 0;
InfiniteTape _infiniteTape;
TapeHead(this._infiniteTape) {}
String next() {
_index += 1;
move(to: _index);
final output = read();
return output;
}
String previous() {
_index -= 1;
move(to: _index);
final output = read();
return output;
}
void move({required int to}) {
this._index = to;
}
String read() {
return _infiniteTape.read(at: this._index);
}
void write(String symbol) {
_infiniteTape.write(symbol: symbol, at: this._index);
}
int index() {
return _index;
}
}
The machine contains “m-configurations” by which it can decide what to do next. In modern parlance, states and state handlers. State handler example:
class FiniteStateControl {
FiniteStateControlDelegate? delegate = null;
void handle({required String symbol}) {
if (symbol == OPCODE_PRINT) {
final argument = delegate?.nextSymbol();
print(argument);
}
else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) {
final to = int.tryParse(delegate!.nextSymbol())!;
final value = new Random().nextInt(to);
delegate!.nextSymbol();
delegate!.write(value.toString());
}
else if (symbol == OPCODE_INPUT_TO_NEXT) {
final input = stdin.readLineSync()!;
delegate?.nextSymbol();
delegate?.write(input);
}
else if (symbol == OPCODE_COPY_FROM_TO) {
final currentIndex = delegate!.index();
и т.д.
After that, you need to create “configurations”, in modern language these are operation codes (opcodes), their handlers. Example opcodes:
const OPCODE_STOP = "stop";
const OPCODE_PRINT = "print";
const OPCODE_INCREMENT_NEXT = "increment next";
const OPCODE_DECREMENT_NEXT = "decrement next";
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal";
const OPCODE_MOVE_TO_INDEX = "move to index";
const OPCODE_COPY_FROM_TO = "copy from index to index";
const OPCODE_INPUT_TO_NEXT = "input to next";
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after";
Don’t forget to create an opcode and a breakpoint handler, otherwise you won’t be able to prove or not prove (sic!) The resolution problem.
Now, using the “mediator” pattern, we connect all the classes in the Turing Machine class, create an instance of the class, record the programs through the tape recorder, load the cassette and you can use it!
For me personally, the question remained interesting, what was primary – the creation of a universal calculator or the proof of the “Entscheidungsproblem” as a result of which, as a by-product, a calculator appeared.
Cassettes
For the sake of entertainment, I recorded several cassette programs for my version of the car.
Hello World
print
hello world
stopСчитаем до 16-ти
increment next
0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stopThe most interesting challenge was writing Quine a program that prints its source code for a single tape machine. For the first 8 hours it seemed to me that this problem could not be solved with such a small number of opcodes, but after only 16 hours it turned out that I was wrong.
Implementation and examples of cassettes, sources below.
Links
https://gitlab.com/demensdeum/turing-machine
References
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
https://kpolyakov.spb.ru/prog/turing.htm
https://www.youtube.com/watch?v=dNRDvLACg5Q
https://www.youtube.com/watch?v=jP3ceURvIYc
https://www.youtube.com/watch?v=9QCJj5QzETI
https://www.youtube.com/watch?v=HeQX2HjkcNo&t=0s
.gif)