覚えておくことができるチューリングマシン

Question

特殊チューリング機は標準チューリング機と同じように定義されており、テープ内の左端からヘッド位置までテープの内容に応じて各ステップが行われます。 （この場合の遷移関数はXΓ* - > Q xγx {L、R}）に属する。

次のうちどれが当てはまります：

a。すべての言語Lは、Lを決定する特別なチューリングマシンがある場合に限り、Lを決定するチューリングマシンを持っています。

b。多項式（入力長多項式）にLを決定する特別なチューリングマシンがある場合に限り、すべての言語LにLを決定するチューリングマシンがあります。

c。 A、Bの答えは正しいです。

d。 A、Bの答えは正しくありません。

と私の質問は： 正しい答えはdです、そして私はなぜ理解できません。

答えは次のとおりです。 各言語は、線形入力長さ時間（Nが入力長さの場合はO（n））の特別なチューリングマシンで決定できます。空白スペースが見られない限り、遷移関数は右側に進み、テープに書き込まれた単語に従って受信または拒否を表示するとすぐに遷移します。

私の質問は： 単語を拒否または受け入れるかどうかを決めるにはどうすればよいですか。 PDA、DFAなどの他の計算モデルでは、遷移機能を同様に定義し、モデルに電力が追加されました。 遷移関数の変化がチューリングマシンになると計算モデルに追加されるように見えるのはなぜですか？

ありがとう。

Answer 1

任意の言語 $ l $ $ t $ があります。 class="math-container"> $ l $ 多項式時間。

チューリングマシンには3つの状態があります。 $ Q_0 $ 、承認状態 $ q_a $ そして拒否状態 $ Q_R $ 。 $ \ gamma $ をテープのアルファベット（空白の記号 $ \ varepsilon $ を含む）にすることができます。 $ \ alpha x $ テープの左端からヘッド位置までテープの内容を表します。ここで、 $ \アルファ\ in \ gamma ^ * $ と $ x \ in \ gamma $ 。いつものように、私は入力がテープの先頭から始めて、そしてヘッドが最初にテープの先頭に配置されていると仮定するつもりです。 遷移関数 $ \ delta $ は次のように定義されています。

• $ \ delta（q_0、\ alpha x）=（q_0、x、r）$ $ x \ NEQ \ VAREPSILON $
• $ \ delta（q_0、\ alpha x）=（q_a、x、r）$ $ x=varepsilon $ と $ \ alpha \ in l $
• $ \ delta（q_0、\ alpha x）=（q_a、x、r）$ $ x=varepsilon $ と $ \ alpha \ not \ in l $

通常のチューリングマシンには未定な言語がありますので、これはすぐにAとBが偽のことを意味します。

答えdとcは不明です。彼らは「両方の回答」について話しますが、あなたは $ 4 $ 可能な答えを与えられています。