Im Jahr 1936 beschrieb der Wissenschaftler Alan Turing in seiner Veröffentlichung „On Computable Numbers, With An Application to Entscheidungsproblem“ den Einsatz einer universellen Rechenmaschine, die dem Problem der Lösbarkeit in der Mathematik ein Ende setzen könnte. Daraus kommt er zu dem Schluss, dass eine solche Maschine nichts richtig lösen könnte, wenn das Ergebnis ihrer Arbeit invertiert und auf sich selbst zurückgeführt würde. Es stellt sich heraus, dass es unmöglich ist, ein *ideales* Antivirenprogramm, einen *idealen* Kachelsetzer, ein Programm, das ideale Phrasen für Ihren Absturz vorschlägt usw. zu erstellen. Paradox!
Diese universelle Rechenmaschine kann jedoch zur Implementierung jedes beliebigen Algorithmus verwendet werden, den sich der britische Geheimdienst zunutze machte, indem er Turing engagierte und die Entwicklung einer „Bombe“-Maschine zur Entschlüsselung deutscher Nachrichten während des Zweiten Weltkriegs ermöglichte.
Das Folgende ist eine OOP-Modellierung eines Einzelbandcomputers in der Dart-Sprache, basierend auf dem Originaldokument.
Eine Turingmaschine besteht aus einem in Abschnitte unterteilten Film, jeder Abschnitt enthält ein Symbol, die Symbole können gelesen oder geschrieben werden. Beispiel einer Filmklasse:
final _map = Map<int, String>();
String read({required int at}) {
return _map[at] ?? "";
}
void write({required String symbol, required int at}) {
_map[at] = symbol;
}
}
Es gibt auch ein „Scan-Quadrat“, es kann sich über den Film bewegen, Informationen lesen oder schreiben, in moderner Sprache – Magnetkopf. Beispiel einer Magnetkopfklasse:
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;
}
}
Die Maschine enthält „M-Konfigurationen“, anhand derer sie entscheiden kann, was als nächstes zu tun ist. In moderner Sprache – Staaten und Zustandsverwalter. Beispiel für einen Statushandler:
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();
и т.д.
Danach müssen Sie „Konfigurationen“ erstellen. In der modernen Sprache sind dies Operationscodes (Opcodes) und ihre Handler. Beispiel-Opcodes:
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";
Vergessen Sie nicht, einen Opcode und einen Stop-Handler zu erstellen, sonst können Sie das Auflösungsproblem nicht beweisen oder nicht beweisen (sic!).
Jetzt verbinden wir mithilfe des „Mediator“-Musters alle Klassen in der Turing-Maschine-Klasse, erstellen eine Instanz der Klasse, zeichnen das Programm mit einem Tonbandgerät auf, laden das Band und Sie können es verwenden!
Für mich persönlich blieb die Frage, was primär war, interessant – Schaffung eines Universalrechners bzw. Beweis des „Entscheidungsproblems“, wodurch als Nebenprodukt ein Rechner entstand.
Kassetten
Zum Spaß habe ich mehrere Kassettenprogramme für meine Version der Maschine aufgenommen.
Hallo Welt
hello world
stopСчитаем до 16-ти
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!
stopСамой интересной задачей было написание Quine программы, которая печатает свой исходный код, для одноленточной машины. Первые 8 часов мне казалось что эта задача не решаема с таким малым количеством опкодов, однако всего через 16 часов оказалось что я был не прав.
Реализация и примеры кассет, источники ниже.
Ссылки
https://gitlab.com/demensdeum/turing-machine
Источники
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
