0

チューリングマシンでは、(異なる)テープが入力と出力の両方に使用され、スタックにも使用されることを知っています。チューリング マシンを使用して 2 つの数値を加算する問題では、入力は 1、0、B(空白)、+ などの多くの記号を処理しています。

(この質問は物理学に関連していますが、チューリングマシンとその入力について知らないかもしれないと思ったので、ここで質問しました。)

入力が BBBBB1111+111111BB の場合、磁気テープでは、

1->北極で表されます(たとえば)。
0->南極で表されます(たとえば)。
B->極性なしで表されます。

では、「+」はどのように表現されるのでしょうか。特殊記号用のコード (ASCII など) があるとは思いません。特殊シンボルの数とタイプは実装に依存するためです。また、特別なコードはアルゴリズムをより退屈なものにします。

また

テープでの入力記号の表現は、上記の方法とはまったく違うのでしょうか? はいの場合、説明してください。

4

2 に答える 2

2

おそらく、各文字を複数のビットでエンコードすることでこれを行うでしょう。例えば:

B: 00
0: 01
1: 10
+: 11

その場合、読み取りヘッドはサイズ 2 になり、移動するときは常に左または右に 2 ステップ移動します。

于 2011-09-09T18:57:47.700 に答える
0
Symbol:  Representation
0:1 ; 1:11 ; 2:111 ; n:n+1 ; Blank:B
于 2012-03-23T02:08:42.997 に答える