問題タブ [turing-machines]

「本格的なKI」とは何ですか？私が理解しているように、それはテキスト分析のためのデータマイニングの一部です。私は正しいですか？いくつかの面白くて便利なリンクで問題ありません！

ありがとうございました！！！

アーサー・デントは、地球上でまだ利用できない宇宙時代の技術を使用して、TM M1 が空のテープで開始されたときに停止するかどうかを判断するアルゴリズムを開発しました。しかしその後、彼は人生、宇宙、そしてすべての意味が42であることを発見しました.

(a) [5] 与えられた TM M2 に対して、Arthur が既に開発したプログラムを使用して、入力 42 で M2 が停止するかどうかを判断できることを証明してください。プルーフで新しい TM を作成する場合は、そのマシン スキーマを指定します。

(b) [5] Arthur のプログラムよりも高速であるが、TM M2 が入力 42 で停止するかどうかという質問に答えるプログラムがあるとします。Arthur がこのアルゴリズムを使用して、空白で開始したときに一部の TM M1 が停止するかどうかを判断する方法を説明してください。テープ。プルーフで新しい TM を作成する場合は、そのマシン スキーマを指定します。

(c) [5] 私たちはクラスで、TM M が空のテープで開始されたときに停止するかどうかを判断する問題は決定できないことを証明しました。TM M が入力 42 で停止するかどうかを判断することも決定不能であることを証明するために使用できるのは、部分 (a) または部分 (b) ですか?

私の教授がここで話していることを解読するのを手伝ってくれる人はいますか?

チューリングマシンのシミュレーターコードを見ていると、次のステートメントに出くわしました

「テープは時間と位置をシンボルにマッピングします。シンボルを計算するには、1ステップ前にマシンを確認する必要があります。その時点で、ヘッドが要求された位置にあった場合、シンボルは表に従って、同じ位置にある前のシンボルとマシンがあった状態。それ以外の場合、シンボルは変更されませんでした。」

イタリック体の部分はどういう意味ですか？この文脈で要求された位置はどういう意味ですか？

チューリングマシンでキューを実装するにはどうすればよいですか？

この問題はNET試験で尋ねられます。

この問題の解決方法を教えてください。問題は、同じ長さの2つの文字列を受け入れることです。

この形式で{q0==>[q0、b、a]のようなチューリングマシンテーブル}で答えたいと思います。

shubhadaa

右にしか動かない（またはとどまる）ことができるチューリングマシンが、標準のチューリングマシンと同じかどうかを確認するように依頼しました。

入力を別のテープにコピーしようと思いましたが、制限はありませんでした。しかし、それは可能ですか？

ありがとう。

チューリングマシンの同等物のリストに関するウィキペディアの記事を見つけました。ただし、特定のマシンがチューリングマシンと同等であるかどうかを判断する方法はわかりません。

それを証明するためにチューリングマシンの定義を使用する必要がありますか？例を挙げていただけますか？

ありがとう。

たまたま、0の文字列を読み取り、バイナリにいくつあるかをテープに書き込むチューリングマシンのアルゴリズムが必要です。

実際には、マシンは実際には0をカウントしないことを認識していますが、その方法についてはかなり困惑しています。

まず、2進数がXか何かで始まる場所をマークする必要があると思います。次に、最初の0に1を書き込み、次の0のそれぞれについて、最下位ビットが0の場合は0になります。 1ですが、1の場合はどうなりますか？たぶんそれを0に変えて、0または空白を見つけて1に変えるまで、すべての1を0に変えて左に進み続けますか？繰り返しになりますが、その場合、LSBに関係なく同じことです。これは、同じことを行うため、0のみが最初の位置になるためです...

うーん...ラバーダック...

任意の数のテープシンボルを含むチューリングマシンMは、{0、1、B}（B =空白）の3つのテープシンボルのみを含む1つのM'でシミュレートできます。

Mは、テープシンボルが2つしかないM "、たとえば{1、B}でシミュレートできますか？

正規表現は、完全ではない言語の古典的な例としてしばしば指摘されます。たとえば、チューリング完全ではない言語を探すこのSOの質問に対する答えとして、「正規表現」が示されています。

ターニングの完全性の概念についての私の、おそらくある程度基本的な理解では、これは、「バランスの取れた」パターンをチェックするために正規表現を使用できないことを意味します。バランスの取れた意味には、終了文字と同じ数の開始文字があります。これを行うには、開始文字と終了文字を一致させるために、何らかの状態が必要になるためです。

ただし、正規表現の.NET実装では、バランスの取れたグループの概念が導入されています。この構成は、前のグループが一致したかどうかをさかのぼって確認できるように設計されています。これは、.NET正規表現が次のことを意味します。

次のようなパターンに一致する可能性があります。

これは、.NETの正規表現がチューリング完全であることを意味しますか？または、言語をチューリング完全にするために必要な、不足している他のものはありますか？