チューリング機械設計0と1

Question

f1（1^n01^m）= 1^| m-n |

途中で0を追跡する方法

を関数（遷移図）を計算チューリングマシンを設計しますか？ 私はそれをしようとしましたが、それを理解することができません

Answer 1

テープアルファベットを0、1、 - （空白）のみで構成するとします。シングルテープのチューリングマシンでは、我々の戦略は実りあるものです。中にある0を前後に跳ね返り、見つけたときに1を横切ります。 1秒が足りなくなり空白になるまで続けます。その時点で、テープに残っているのはすべて1^| m-n |です。 n + m + 1- | m-n |ゼロ。最後に、結果をテープの先頭にコピーします（既に存在していない場合、つまりm> nの場合）。ゼロを消去します。

Q s s' D Q' 

// read past 1^n 
q0 1 1 R q0 

// read through zeroes 
q0 0 0 R q1 
q1 0 0 R q1 

// mark out the first 1 remaining in 1^m 
q1 1 0 L q2 

// read through zeros backwards 
q2 0 0 L q2 

// mark out the last 1 remaining in 1^n 
q2 1 0 R q1 

// we were reading through zeroes forward 
// and didn't find another 1. n >= m and 
// we have deleted the same number from 
// the first and last parts so just delete 
// zeroes 
q1 - - L q3 
q3 0 - L q3 
q3 1 1 L halt_accept 

// we were reading through zeroes backwards 
// and didn't find another 1. n < m and we 
// accidentally deleted one too many symbols 
// from the 1^m part. write it back and start 
// copying the 1s from after the 0s back to 
// the beginning of the tape. then, clear zeroes. 
q2 - - R q4 
q4 0 1 R q5 
q5 0 0 R q5 
q5 1 0 L q6 
q6 0 0 L q6 
q6 1 1 R q4 
q5 - - L q7 
q7 0 - L q7 
q7 1 1 L halt_accept 

当然ながら、TMの例は、その実行例なしでは完全ではありません。

-111110111- => -111110111- => -111110111- 
^     ^    ^
q0     q0     q0 

=> -111110111- => -111110111- => -111110111- 
     ^    ^    ^
     q0     q0     q0 

=> -111110111- => -111110011- => -111110011- 
      ^    ^    ^
      q1    q2    q2 

=> -111100011- => -111100011- => -111100011- 
     ^    ^    ^
      q1     q1     q1 

=> -111100001- => -111100001- => -111100001- 
      ^    ^    ^
      q2    q2    q2 

=> -111100001- => -111000001- => -111000001- 
     ^    ^    ^
     q1     q1     q1 

=> -111000001- => -111000001- => -111000001- 
      ^    ^    ^
      q1     q1     q1 

=> -111000000- => -111000000- => -111000000- 
      ^    ^    ^
      q2     q2    q2 

=> -111000000- => -111000000- => -111000000- 
     ^    ^    ^
      q2     q2    q2 

=> -110000000- => -110000000- => -110000000- 
     ^    ^    ^
     q1     q1     q1 

=> -110000000- => -110000000- => -110000000- 
      ^    ^    ^
      q1     q1     q1 

=> -110000000- => -110000000- => -11000000-- 
      ^    ^    ^
       q1    q3    q3 

=> -1100000--- => -110000---- => -11000----- 
      ^    ^    ^
      q1    q3    q3 

=> -1100------ => -110------- => -11-------- 
     ^    ^    ^
     q1    q3    q3 

=> -11-------- 
    ^
     halt_accept