n> = 1チューリングマシンの場合1^3^n

Question

3の長さの1の弦を受け入れるチューリングマシンを作りたい。111,111111111,111111111111111111111111111など。しかし、私はこのためのアルゴリズムを作ることができません。これまで私は3の倍数を受け入れる機械を作ることができました。親切に助けてください

Answer 1

入力の長さ（111,111111111、...）がstrLenであることを確認してください。 log（strLen）の結果が基数3に等しいことを点検します。

すなわち、コードで：任意のプログラミングタスクと同様に

bool is_integer(float k) { return std::floor(k) == k; }

if(is_integer(log(strLen)/log(3))){ //Then accept the string as it's length is a power of 3. }

Answer 2

、あなたの目標は、あなたが解決することができる小さな問題にタスクを破るそれらを解決し、作品を置くことです一緒に、より困難な問題に答える。これを行う方法はたくさんありますが、一般的には、あなたに合ったものを見つけなければなりません。そして、それだけで、「より良い」「より速い」プログラムを得ることを心配すべきでしょうか。

何が3の累乗になるのでしょうか？数が3の累乗である場合

1. ナンバーワン三（3^0）
2. の力で、3倍の数は3（X = 3^K => 3X =の力であります3 ^（k + 1））。

帰納的な定義ではなく、帰納的な定義を与えるために、上記の2方向を「逆転」することができます。3は3で割り切れ、3で割った数がべき乗（3 | x & & x/3 = 3k k => x = 3 ^（k + 1））の3つの値を持つ。テープは単一のものを持っているかどうかを確認するために

1. チェック：

   これは、次のように動作チューリングマシンを示唆しています。もしそうなら、halt-accept。

2. それ以外の場合は、3で割り、テープヘッドを先頭にリセットしてからやり直してください。

どのように3つに分割できますか？さて、私たちは1つを数えることができ、その後に2つを消去することができます。カウントした数の2倍の数だけ消去すると、元の数の3分の1になります。しかし、消えるものがなくなると、その数は3で割り切れないことがわかります。停止することができます。

これは私たちのデザインです。今は実装の時間です。私たちは2つのフェーズを持つでしょう：第1フェーズは、1つのフェーズをチェックします。もう一方の位相は3で割ってテープヘッドをリセットします。分割するときは、空白のセルと区別できる新しいテープ記号Bを挿入して消去します。これは重要なことですので、入力の開始と終了の場所を覚えることができます。

Q T | Q' T' D 
----------+----------------- 
// phase one: check for 3^0 
----------+----------------- 
q0 # | h_r #  S // empty tape, not a power of three 
q0 1 | q1 1  R // see the required one 
q0 B | h_r B  S // unreachable configuration; invalid tape 
q1 # | h_a #  L // saw a single one; 1 = 3^0, accept 
q1 1 | q2 1  L // saw another one; must divide by 3 
q1 B | q1 B  R // ignore previously erased ones 
----------+----------------- 
// prepare for phase two 
----------+----------------- 
q2 # | q3 #  R // reached beginning of tape 
q2 1 | q2 1  L // ignore tape and move left 
q2 B | q2 B  L // ignore tape and move left 
---------------------------- 
// phase two: divide by 3 
---------------------------- 
q3 # | q6 #  L // dividing completed successfully 
q3 1 | q4 1  R // see the 1st one 
q3 B | q3 B  R // ignore previously erased ones 
q4 # | h_r #  S // dividing fails; missing 2nd one 
q4 1 | q5 B  R // see the 2nd one 
q4 B | q4 B  R // ignore previously erased ones 
q5 # | h_r #  S // dividing fails; missing 3rd one 
q5 1 | q3 B  R // see the 3rd one 
q5 B | q5 B  R // ignore previously erased one 
----------+----------------- 
// prepare for phase one 
----------+----------------- 
q6 # | q0 #  R // reached beginning of tape 
q6 1 | q6 1  L // ignore tape and move left 
q6 B | q6 B  L // ignore tape and move left 

いくつかのバグがあるかもしれませんが、基本的には思った通りだと思います。