machine

1936 年，科学家艾伦·图灵在他的出版物《论可计算数，及其在解决问题中的应用》中描述了通用计算机的使用，它可以解决数学中的可解性问题。结果，他得出的结论是，如果这种机器的工作结果被颠倒并循环回自身，那么它就无法正确解决任何问题。事实证明，不可能创建一个“理想的”防病毒软件、一个“理想的”磁贴设置器、一个为您的崩溃建议理想短语的程序等等。悖论！

然而，这种通用计算机可以用来实现任何算法，英国情报部门利用了这一点，雇佣了图灵并允许创建“Bombe”机器来破译第二次世界大战期间的德国信息。

以下是基于原始文档，使用 Dart 语言对单磁带计算机进行 OOP 建模。

图灵机由分成多个部分的薄膜组成，每个部分包含一个符号，这些符号可以读取或写入。电影类示例：

final _map = Map<int, String>(); 

  String read({required int at}) { 
    return _map[at] ?? ""; 
  } 

  void write({required String symbol, required int at}) { 
    _map[at] = symbol; 
  } 
}

还有一个“扫描方块”，它可以在胶片上移动，读取或写入信息，用现代语言来说就是——磁头。磁头类示例：

  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; 
  } 
}

机器包含“m-configurations”，通过它可以决定下一步做什么。用现代语言来说——状态和状态处理程序。状态处理程序示例：

  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(); 

и т.д.

之后，您需要创建“配置”，用现代语言来说，这些是操作代码（操作码）及其处理程序。操作码示例：

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";

不要忘记创建操作码和停止处理程序，否则您将无法证明或无法证明（原文如此！）解决问题。

现在，使用“中介者”模式，我们连接图灵机类中的所有类，创建该类的实例，通过磁带录音机录制程序，加载磁带就可以使用它了！

对我个人来说，什么是主要的问题仍然很有趣——“什么是主要的”？创建通用计算器或“Entscheidungsproblem”的证明，作为副产品，计算器出现了。

盒式磁带

为了好玩，我为我的机器版本录制了几个盒式磁带节目。

你好世界

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

Tag Archives: machine

图灵炸弹

盒式磁带

Ссылки

Источники