チューリングマシンとは

https://stackoverflow.com/questions/236000

04-07-2019
|

質問

チューリングマシンとは何ですか？なぜ人々はそれを言及し続けるのですか？計算に必要なのは私のIBM PCだけです！なぜ誰もがこれらのマシンを気にするのですか？

解決

チューリングマシンが重要な理由は、古典的なコンピューティングサイエンスまたは計算理論の種類の研究に関係しています。基本的には、コンピューターの理論的な能力や制限など、コンピューターの一般的な特性を分析することと、<！> quot; computing <！> quotについて話すときの意味についてです。何か。

Turing Machinesを使用して学習できる例の1つは、停止の問題です。この問題はアカデミックな課題ですが、現実の世界では容易に具体的な意味を持ちます。プログラムに無限ループが含まれているかどうかを単に知らせるデバッガーを作成してみませんか？停止問題は、この問題を一般的なケースで解決することは不可能であることを証明しています。

チューリングマシンの研究は、言語の文法とそのクラスの研究にも役立ち、プログラミング言語の開発につながります。用語<！> quot;正規表現<！> quot;それらは通常の文法であり、これらの文法の研究（計算理論の一部））正規表現で解決できる問題とできない問題を正確に説明します。たとえば、従来の正規表現の構文では、次の問題を解決できません。入力内のいくつかのN個の 'a'文字を解析し、次に同じ数Nのchar 'b'を解析します。

この種のことに関する良いテキストに興味がある場合は、はじめにマイケル・シプサーによる計算理論へ。良いです。

他のヒント

チューリングマシンは、数学計算の理想的なモデルとして機能するためにアランチューリングによって発明された理論的な計算機であり、基本的にはコンピューターの単純な形式であり、テープ（紙のリボン）、シンボルの読み取り、新しいシンボルの書き込み、および左または右への移動が可能なヘッドを備えています。

チューリングマシンは特定の状態にあると言われ、プログラムは現在の状態と頭の下にシンボルがある遷移のリストです。テープに書き込む内容、次の状態、ヘッドを移動する場所。

これは基本的なチューリングマシンで、JavaScriptで実装されています...

そしてスケッチ：

turing machine

計算に必要なのはIBM PCだけです！

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

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

（一般的に受け入れられている）<！> quot;教会チューリング論文<！> quot;計算のすべてのデバイスまたはモデルはチューリングマシンほど強力ではないと断言します。そのため、多くの理論的な問題（PやNPなどのクラス、<！> quot;多項式時間アルゴリズム<！> quot;など）は、チューリングマシンに関して正式に述べられていますが、もちろん、他のモデルにも適用できます。（たとえば、ラムダ計算や組み合わせ論理などの観点から計算を考えると便利な場合があります。これらはすべて互いに、そしてIBM PCとも同等の能力を持っています。）

これで、チューリングマシンについて話すことができます。これは、<！> quot; computer <！> quot; CPUのアーキテクチャやその制約などの詳細をすべて説明する必要はありません。

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

最初に、いくつかの背景：

RNAは次の文字列で構成されています定義するヌクレオチド（<！> quot; bases <！> quot;）遺伝的アルファベットの文字。
RNAには4つの塩基がありますアルファベット-A、C、G、U。
ベースは方向性：によって終わりは呼ばれる慣習 5プライムと3プライム（5 '、3'）
RNAストリングの塩基は、別のRNAストリングの塩基を<！> quot;アンチパラレル相補的に引き付けることができますペア<！> quot;、AはUに、CはGに固定されます。
ベースは次のグループにまとめられます 3 <！> quot; codons <！> quot; （単語）。
可能な組み合わせは64個ありますコドン（4 ^ 3）。
各コドンは<！> quot; anti-codon <！> quot;と一致できます。たとえば、AUG <！> lt;-<！> gt; UAC
特別なキャリア分子があります（<！> quot; tRNA <！> quot;）特定のアンチコドンとに接続されています特定のアミノ酸（タンパク質）。

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

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

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

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

チューリングマシンは、実際のコンピューター（IBM PCなど）では達成できないことを発見するのに役立つので、気にしています。チューリングマシンが特定の計算を実行できない場合（ Halting Problem を決定するなど）、 IBM PCが同じ計算を実行することは不可能であると考えるのが妥当です。

なぜ飛行機を設計する人々がライト兄弟、または<！> quot; lift <！> quot;の背後にある科学を気にするのでしょうか。固定翼の航空機が飛ぶことができますか？

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

計算可能性の理論は大学で最も難しいクラスでしたが、それを受け入れて良かったです。それは、私が決して持っていなかったものについて考えさせたり、私が決して持っていないであろう方法で物事を考えさせたり、それらは良いことです。

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

ウィキペディアから：

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

他のチューリングマシンをシミュレートできるチューリングマシンは、ユニバーサルチューリングマシン（UTM、または単にユニバーサルマシン）と呼ばれます。同様の<！> quot; universal <！> quot;を持つ、より数学的な定義自然は、アロンツォ教会によって導入されました。ラムダ計算の研究は、チューリングの公式の計算理論の中でチューリングの仕事と絡み合っています。論文は、チューリング機械が実際に論理および数学における効果的な方法の非公式の概念を捕らえ、アルゴリズムまたは「機械的手順」の正確な定義を提供すると述べています。

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

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

ほとんどの場合、思考の糧。

Wikipediaのエントリに加えて、本注釈付きCharles Petzoldによるチューリング。字幕付き<！> quot; Alan Turingの計算可能性とチューリングマシンに関する歴史的論文のガイド付きツアー<！> quot ;、これには完全な論文が含まれており、歴史的な観点を含むトピックに関する多くの議論が含まれています。 p>

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

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow