CoQのような非耕作の完全な言語の実際的な制限は何ですか？

StackOverflow https://stackoverflow.com/questions/3492188

質問

そこには非耕作言語があり、大学でcompSciを勉強しなかったので、誰かがチューリングに不完全な言語を説明できますか（ coq）できませんか？

または、現実の完全性/不完全性です 実用的 関心（つまり、それは実際にはそれほど違いはありませんか）？

編集 - 私はの線に沿って答えを探しています xのために、非耕作用の完全な言語でハッシュテーブルを構築することはできません, 、またはそのようなもの！

役に立ちましたか？

解決

まず、あなたはすでに聞いたことがあると思います 教会の教会の論文, 、私たちが「計算」と呼ぶものはすべて、チューリングマシン（または他の多くの同等のモデル）で行うことができることを示しています。したがって、チューリング完了言語は、任意の計算を表すことができる言語です。逆に、チューリングに不完全な言語は、表現できない計算があるものです。

わかりました、それはあまり有益ではありませんでした。例を挙げましょう。チューリングインクロクト言語ではできないことは1つあります。チューリングマシンシミュレーターを書くことはできません（それ以外の場合は、シミュレーションされたチューリングマシンで計算をエンコードできます）。

わかりました、それ まだ あまり有益ではありませんでした。本当の質問は、何ですか 使える プログラムは、チューリングには不完全な言語で書くことができませんか？まあ、誰かが有用な目的のために書いたすべてのプログラムを含む「有用なプログラム」の定義を思いついた人はいません。したがって、すべての有用なプログラムを書くことができるチューリングインクロクト言語を設計することは、非常に長期的な研究目標です。

現在、いくつかの非常に異なる種類のチューリングが不完全な言語があり、それらができないことは異なります。ただし、共通のテーマがあります。言語を設計している場合、言語がチューリングが完全になるようにするための2つの主要な方法があります。

  • 言語に任意のループがあることが必要です（while）および動的メモリ割り当て（malloc)

  • 言語が任意の再帰関数をサポートすることを要求します

それにもかかわらず、一部の人々がプログラミング言語と呼ぶかもしれない非耕作の完全な言語のいくつかの例を見てみましょう。

  • Fortranの初期バージョンには、動的なメモリ割り当てがありませんでした。計算が必要なメモリの量を事前に把握し、それを割り当てる必要がありました。それにもかかわらず、Fortranはかつて最も広く使用されているプログラミング言語でした。

    明らかな実際的な制限は、プログラムを実行する前にメモリ要件を予測する必要があることです。それは難しい場合があり、入力データのサイズが事前に制限されていない場合、不可能になる可能性があります。当時、入力データに供給している人は、多くの場合、プログラムを書いた人であったため、それほど大したことではありませんでした。しかし、それは今日書かれたほとんどのプログラムには当てはまりません。

  • Coqは、ために設計された言語です 定理を証明します. 。今 定理とランニングプログラムの証明は非常に密接に関連しています, 、そのため、定理を証明するのと同じように、CoQでプログラムを書くことができます。直感的には、定理の証明「Aはb」とは、定理aの証拠を議論として採用し、定理Bの証明を返す関数である。

    システムの目標は定理を証明することであるため、プログラマに任意の関数を書くことはできません。言語が、自分自身と呼ばれるばかりの愚かな再帰関数を書くことを許可したことを想像してください（お気に入りの言語を使用する行を選択してください）：

    theorem_B boom (theorem_A a) { return boom(a); }
let rec boom (a : theorem_A) : theorem_B = boom (a)
def boom(a): boom(a)
(define (boom a) (boom a))

    そのような関数の存在が、AがBを暗示することをあなたに納得させることはできません。さもなければ、あなたは真の定理だけでなく、何でも証明することができます！したがって、coq（および同様の定理プロバー）は、arbitrary意的な再帰を禁止します。再帰関数を書くときは、必要です それが常に終了することを証明します, 、だから、定理の証拠でそれを実行するたびに、それが定理Bの証拠を構築することを知っている。

    COQの実際の実際の制限は、任意の再帰関数を書くことができないことです。システムはすべての非終了機能を拒否できる必要があるため、 停止の問題 （より一般的に ご飯の定理）拒否された機能が終了することを保証します。追加の実際的な難しさは、あなたの関数が終了することを証明するためにシステムが支援する必要があることです。

    AからBへの関数がある場合、AがB.を暗示する数学的証拠と同じくらい良いという保証を妥協することなく、証明システムをよりプログラミング言語のようにすることに関する多くの継続的な研究があります。終了機能は、研究トピックの1つです。その他の拡張指示には、入力/出力や並行性などの「現実世界」の懸念への対処が含まれます。もう1つの課題は、これらのシステムを単なる人間がアクセスできるようにすることです（または、実際にアクセス可能であることを単なる人間に納得させるかもしれません）。

  • 同期プログラミング言語 リアルタイムシステムをプログラミングするために設計された言語、つまり、プログラムが以下で応答する必要があるシステムは n クロックサイクル。これらは、主に車両制御やシグナリングなどのミッションクリティカルなシステムに使用されます。これらの言語は、プログラムの実行にかかる時間と、どのくらいのメモリが割り当てられるかについて、強力な保証を提供します。

    もちろん、このような強力な保証のカウンターパートは、事前に予測できないメモリの消費と実行時間のプログラムを書くことができないことです。特に、メモリの消費または実行時間が入力データに依存するプログラムを作成することはできません。

  • 言語をプログラミングしようとさえしない専門言語がたくさんあります。そのため、正規表現、データ言語、ほとんどのマークアップ言語、...

ところで、 ダグラス・ホフスタッター 特に、計算に関する非常に興味深い人気のある科学の本をいくつか書きました ゲーデル、エッシャー、バッハ：永遠の黄金の三つ編み. 。彼がチューリングの不完全性の制限を明示的に議論するかどうかは覚えていませんが、彼の本を読むことは、あなたがより技術的な資料を理解するのに間違いなく役立ちます。

他のヒント

最も直接的な答えは、チューリングが完了していないマシン/言語を使用して、チューリングマシンを実装/シミュレートすることはできません。これは、チューリングの完全性の基本的な定義から来ています。マシン/言語は、チューリングマシンを実装/シミュレートできる場合、完全にチューリングを行っています。

それで、実際の意味は何ですか？まあ、チューリングを完全にすることが示されることができるものはすべて、すべての計算可能な問題を解決できるという証拠があります。定義上、チューリングが完了していないものはすべて、解決できない計算可能な問題があるというハンディキャップを持っていることを意味します。これらの問題は、システムが非耕作を完了するものに欠けている機能に依存します。

たとえば、言語がループや再帰をサポートしていない場合、または暗黙のうちにループを完全にチューリングすることはできません。したがって、その言語はループを必要とする問題を解決することができません。

別の例は、言語がリストや配列をサポートしていない場合（または、ファイルシステムを使用するなどのエミュレートすることを許可します）、チューリングマシンにはメモリへの任意のランダムアクセスが必要なため、チューリングマシンを実装できません。したがって、その言語は、メモリへの任意のランダムアクセスを必要とする問題を解決することができません。

したがって、言語を非耕作するように分類する機能が欠けている機能は、言語の有用性を実際に制限するまさにそのことです。答えは、それが依存するということです：何が言語を非耕作しないのですか？

COQなどの言語に適している問題の重要なクラスは、終了が推測されるか、証明するのが難しいものです。あなたは数の理論でたくさんの例を見つけることができます、多分最も有名なのは コラッツの推測

function collatz(n)
  while n > 1
    if n is odd then
      set n = 3n + 1
    else
      set n = n / 2
    endif
 endwhile

この制限は、COQでより自然でない方法でそのような問題を表現する必要があります。

チューリングマシンをシミュレートする関数を書くことはできません。チューリングマシンをシミュレートする関数を書くことができます 2^128 （また 2^2^2^2^128 手順）およびチューリングマシンが許可されたステップ数よりも長く承認、拒否、または実行されたかどうかを報告します。

「実際に」以来、コンピュータがチューリングマシンをシミュレートできるようになるまでは長い間なくなります。 2^128 ステップ、チューリングの不完全性は「実際に」「実際に」大きな違いをもたらさないと言うのは公平です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top