9

私がマシンを持っている場合、それをマシン1と呼びます。これは、問題を解決することができます。それは単なるマシンであり、それ自体はチューリングマシンではありません。それは1つの特定の問題を解決することができます。これとまったく同じ問題が万能チューリングマシンで解決できる場合、私の元のマシン1は万能チューリングマシンでもありますか?

これは、すでに解決されているすべての問題に当てはまるわけではありません。この記述された特性を持っている問題はありますか?それが絶対に真実ではない場合、なぜですか?

誰かが解決すべき問題の例を挙げてもらえますか?この問題が私の元のマシン1で解決された場合、間違いなくこれをユニバーサルターニングマシンにしますか?それともそのような問題は存在しませんか?それが存在しない場合、なぜですか?

とても興味がありますが、わかりません…ありがとうございます。

編集:質問をより明確にしました。

4

7 に答える 7

5

万能チューリング機械は、あらゆる種類の問題を解決できます。

あなたのmachine(1)が1 + 1を解くことができるなら、それはそれが巨大なクラスのどれでも解くことができるという意味ではありません。したがって、万能チューリング機械ではない可能性があります。

于 2010-01-20T12:15:50.250 に答える
2

論理学者は、「十分な」条件と「必要な」条件を区別します。たとえば、次の文を見てください

空は青い。

(それが常に真実であると仮定しましょう)。あなたが今知っているのはこれです:

空を見ると青い色が見えます。

あなたが知らないのはこれです:

あなたが青い色を見るとき、あなたは空を見ています。

-隣人の車を見ている方がいいかもしれません。

論理的には、空には青が必要ですが、それだけでは不十分です。

同じことがあなたの場合にも当てはまります:マシン(1)はあなたの問題を解決するので、それは確かに解決可能な問題です。したがって、問題を解決できることはUTMにとって必要条件ですが、UTMはこの単一の問題だけでなく、あらゆる問題を解決できなければならないため、十分ではありません。

于 2010-01-20T12:26:34.723 に答える
1

特定のシステムのチューリング完全性を証明することは、チューリング完全であることがわかっている別のシステムと同等/同型であることを簡単に示すことができない限り、簡単ではありません。簡単な答えです。チューリング完全であるかどうかを確認するためにマシンを通過させることができる簡単なテストはありません。システム全体のプロパティを分析して表示する必要があります。

このトピックについて詳しく知りたい場合は、チューリング完全性と計算可能性理論に関するこれらの記事を読んでください。

于 2010-04-03T04:01:40.283 に答える
1

万能チューリングマシンは、特定のチューリングマシンが解決できるコードを解決できます。

したがって、万能チューリングマシン(2)は、元のチューリングマシン(1)が解決するように設計された問題を解決できます。

ただし、元のチューリングマシン(1)は、その正確な問題のみを解決でき、他の問題(万能チューリングマシンであるという「問題」を含む)を解決することはできません。

ですから、あなたの説明によれば、あなたのオリジナルのチューリングマシンは万能チューリングマシンではありません。(あなたがそれを定義した場合かもしれませんが、それは一種の不正行為です)。

于 2010-01-20T12:14:05.390 に答える
1

Universal Turning Machine(UTM)のポイントは、どのチューリングマシン(TM)でも、そのTMを取得して、TMの動作を説明するエンコーディングを作成し、そのエンコーディングを別のTMで実行できることです。

UTMは、他のTM定義を書き換えることができるほど強力な定義を持つTMです。

UTMをインタプリタと考えてください。TMは特定のタスクです。

TMも通訳者のクラスに属していない限り、UTMでもありません。(UTMも特別にタスクされたTMであるため)。

したがって、2番目の質問に答えるには、UTMとTMが同等であることを示すことができれば、TMもUTMであることを示したことになります。これを行うには、UTMのエンコードされたプログラムをTMの同等のプログラムに変更する方法を示すことができる必要があります。

于 2010-01-20T12:20:18.757 に答える
1

誰かが解決すべき問題の例を挙げてもらえますか?

確かに:エンコードされた旋盤とデータを考えると、結果はどうなりますか:)お使いのマシンがこの問題を解決できるのであれば、それは確かにUTMです。

これらのさまざまな問題がNPにある理由の線を知っていますか?「ハミルトン閉路問題を解く機械を持っているときに、3サット問題を解くことができますか?」のように。あなたは確かにあなたの質問に答えるために同じものを使うことができます。

于 2010-01-20T12:33:41.550 に答える
1

チューリングマシンをシミュレートするためのコード(高レベル)を作成する必要がある場合、UTMをどのように進めるかを想像してください。次のものが必要になります。1。入力シンボルとyiuが実行するものを保持する配列。2.ユーザーにプロンプ​​トを表示する遷移関数を保持する配列(2-dの可能性あり)。3.遷移関数のユーザー入力を読み取り、配列1でシミュレートするアルゴリズム。4。プログラムが自身の状態を追跡するために必要な変数はほとんどありません。

このように考えると、完全に機能するコードを取得することになれば、完全なUTMになります。ただし、コードをどれだけ効率的にコーディングしても、ユーザーが遷移関数を入力してコードが永久に実行されるのを防ぐことはできません。そのため、UTMが失敗する特定の問題が発生します。これらの問題については、次のように述べています。会員試験機を開発することはできません(ただし、会員確認機はいつでも可能です)

于 2011-12-06T02:46:24.787 に答える