computer science Archives

1936 年、科学者のアランチューリングは、著書『計算可能な数について、現実の問題への応用』の中で、数学における可解性の問題に終止符を打つ可能性のある万能計算機の使用について説明しました。その結果、彼は、そのようなマシンの作業結果が反転され、それ自体でループバックされる場合、そのようなマシンは何も正しく解決できないだろうという結論に達しました。 *理想的な* アンチウイルス、*理想的な* タイルセッター、クラッシュに対して理想的なフレーズを提案するプログラムなどを作成するのは不可能であることが判明しました。パラドックス！

しかし、この汎用コンピューティングマシンはあらゆるアルゴリズムの実装に使用でき、英国諜報機関はそれを利用してチューリングを雇い、第二次世界大戦中にドイツのメッセージを解読するための「ボンベ」マシンの作成を許可しました。

以下は、元のドキュメントに基づいた、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 構成」が含まれています。現代語で–状態と状態ハンドラー。状態ハンドラーの例:

  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: computer science

チューリング爆弾

カセット

Ссылки

Источники