computer-science - チューリングマシンとは？

Question

チューリングマシンとは何ですか?なぜ人々はそれについて言及し続けるのですか? IBM PC だけで計算を行うことができます。なぜ誰もがこれらのマシンを気にするのですか?

score 60 · Accepted Answer

チューリングマシンが大したことである理由は、古典的な計算科学または計算理論タイプのものの研究と関係があります。基本的には、コンピュータの一般的な特性を分析することです。たとえば、コンピュータの理論的能力や限界、何かを「計算する」という場合の意味などです。

チューリングマシンを使用して研究できるものの 1 つの例は、停止問題です。この問題は学問的な課題のようなものですが、実際の世界に影響を与えることは容易に理解できます。プログラムに無限ループが含まれているかどうかを単純に通知するデバッガを作成してみませんか? 停止問題は、一般的なケースでこの問題を解決することは不可能であることを立証しています。

チューリングマシンの研究は、プログラミング言語の開発につながる言語の文法とそのクラスの研究にも役立ちます。「正規表現」という用語は、それらが正規文法であることから生まれました。これらの文法 (計算理論の一部) を研究することで、正規表現で解決できる問題と解決できない問題の正確な種類について詳しく知ることができます。たとえば、従来の正規表現の構文では、次の問題を解決できません。入力の「a」文字の数 N を解析し、次に同じ数 N の文字「b」を解析します。

この種の優れたテキストに興味がある場合は、Michael Sipser による計算理論の紹介をご覧ください。それは良いです。

score 33 · Accepted Answer

チューリングマシンは、数学計算の理想化されたモデルとして機能するためにアランチューリングによって発明された理論計算機です。基本的には、テープ(紙のリボン) で構成された単純な形式のコンピューターで、記号を読み取ることができるヘッドを備えています。、新しい記号を所定の位置に書き、左または右に移動します。

チューリングマシンは特定の状態にあると言われ、プログラムは遷移のリストであり、現在の状態と頭の下の記号、テープに何を書くべきか、次の状態は何か、そしてどこにあるのかを持っています頭が動くはずです。

これは、 JavaScript で実装されたBasic Turing Machineです...

そしてスケッチ：

チューリングマシン

score 28 · Accepted Answer

IBM PC だけで計算を行うことができます。

他の人が指摘していないこと: あなたの IBM PCはチューリングマシンです。もっと正確に言えば、PC ができることは何でもチューリングマシンができるという意味で、チューリングマシンができることは何でも PC もできるという意味で、それと同等です。

具体的に言うと、チューリングマシンは、計算可能性の概念を完全に捉えた計算のモデルであり、PC のアーキテクチャの特定の詳細がなくても、簡単に推論できます。

（一般に受け入れられている）「チャーチ・チューリングのテーゼ」は、計算のすべてのデバイスまたはモデルは、チューリング・マシンよりも強力ではないと主張しています。そのため、多くの理論的問題 (たとえば、P や NP などのクラス、「多項式時間アルゴリズム」の概念など) は、チューリングマシンの観点から正式に記述されていますが、もちろん、他のモデルに適用することもできます。良い。(たとえば、ラムダ計算や組み合わせ論理などの観点から計算を考えると便利な場合があります。これらはすべて、相互に同等であり、IBM PC に対しても同様です。)

つまり、CPU のアーキテクチャやその制約などのすべての詳細を説明する必要がなく、「コンピューター」が何であるかを正確かつ完全に指定した方法であるため、人々はチューリングマシンについて話します。

score 27 · Accepted Answer

実際、自然界にはチューリングマシンの例があります。具体的には、RNA をタンパク質に翻訳するリボソームがチューリングマシンを実装しています。

まず、いくつかの背景:

RNA は、遺伝的アルファベットの文字を定義する一連のヌクレオチド (「塩基」) で構成されています。
RNA アルファベットには、A、C、G、U の 4 つの塩基があります。
塩基には方向性があります: 慣例により、末端は 5 プライムおよび 3 プライム (5', 3') と呼ばれます。
RNA ストリングの塩基は、A が U にくっつき、C が G にくっつく「逆平行相補対」で、別の RNA ストリングの塩基を引き付けることができます。
塩基は 3 つのグループで結合されて「コドン」 (単語) を形成します。
コドンには 64 通りの組み合わせ (4^3) があります。
各コドンは「アンチコドン」と一致できます。たとえば、AUG <-> UAC
特定のアンチコドンを持ち、特定のアミノ酸 (タンパク質) に結合している特別な担体分子 (「tRNA」) があります。

リボソームの操作は簡単です。

転写は、「リーディングフレーム」を定義する「開始コドン」で開始されます。
転写は常に 5'->3' 方向に進行します
リーディングフレームの下のコドンは、特定のアミノ酸を含む特定の tRNA と一致します。
開始コドンは常にアミノ酸のメチオニンをコードしています。
新しいアミノ酸は成長中のタンパク質に付着します
フレームは次のコドンに 3 塩基進み、タンパク質は連続的に伸長されます。
「停止」コドンに遭遇すると、翻訳が終了し、アミノ酸が結合されなくなり、リボソームがmRNAから解離します。

ご覧のとおり、これは非常に単純なチューリングマシンであり、最も複雑な操作である自然そのものを実行します。

score 6 · Accepted Answer

チューリングマシンは、コンピューターの限界について推論するために使用できる理論上のマシンです。簡単に言えば、無限のメモリを備えた架空のコンピューターです。

私たちがチューリングマシンに関心を持っているのは、実際のコンピューター (IBM PC など) では達成できないことを発見するのに役立つからです。チューリングマシンが特定の計算を実行できない場合 (停止問題の決定など)、IBM PC で同じ計算を実行することは不可能です。

score 3 · Accepted Answer

飛行機を設計する人々が、なぜライト兄弟や、固定翼航空機を飛ばす「揚力」の背後にある科学に関心を持つのでしょうか?

アラン・チューリングは、現代コンピューティングの父として称賛されています。チューリングマシンは、現在のすべてのコンピューターの前身です。

計算可能性の理論は、大学での私の最も難しいクラスでしたが、受けてよかったです。考えたことのないことについて考えさせられたり、考えたことのない方法で考えさせられたりしました。

score 2 · Accepted Answer

チューリングマシンは、計算が可能な抽象的なマシンです。

ウィキペディアから:

チューリングマシンは基本的な抽象記号操作デバイスであり、その単純さにもかかわらず、任意のコンピューターアルゴリズムのロジックをシミュレートするように適合させることができます。それらは1936年にアラン・チューリングによって記述されました。チューリングマシンは、実用的なコンピューティングテクノロジとして意図されたものではなく、機械的計算の限界についての思考実験です。したがって、それらは実際には構築されませんでした。それらの抽象的な特性を研究することで、コンピューターサイエンスと複雑性理論に関する多くの洞察が得られます。

他のチューリングマシンをシミュレートできるチューリングマシンは、ユニバーサルチューリングマシン (UTM、または単にユニバーサルマシン) と呼ばれます。同様の「普遍的な」性質を持つ、より数学的な定義がアロンゾ・チャーチによって導入されました。彼のラムダ計算に関する研究は、チャーチ・チューリングのテーゼとして知られる形式的な計算理論でチューリングのものと絡み合っていました。この論文では、チューリングマシンが実際に論理と数学における効果的な方法の非公式な概念を捉えており、アルゴリズムまたは「機械的手順」の正確な定義を提供していると述べています。

score 2 · Accepted Answer

チューリングマシンは、一連のデータを操作できる抽象マシンであり、ロジックに従って、操作中にデータだけでなく自身の状態も変更できます。

これは、アルゴリズム、ストアドプログラム、計算全般の基礎となる概念です。アルゴリズム、状態、データなどを扱っている場合、優れた洞察と抽象化を提供します。

ほとんどの人にとって、考える材料です。

score 1 · Accepted Answer

ウィキペディアのエントリに加えて、チャールズ・ペッツォルドの「注釈付きチューリング」という本を手に入れたいと思うかもしれません。「計算可能性とチューリングマシンに関するアランチューリングの歴史的な論文のガイド付きツアー」というタイトルで、歴史的な視点を含むトピックに関する多くの談話を含むチャンクに分割された完全な論文が含まれています。

score 1 · Accepted Answer

チューリングマシンはアルゴリズムに相当します。文字列を受け入れると停止し、文字列を受け入れない場合は拒否するか、無限ループに入ります。

テープはメモリとして機能し、遷移ルールは「if then else」条件として機能します

computer-science - チューリングマシンとは？

11 に答える 11

Related

Reference