terminology - 「完全な」プログラミング言語の用語?

Question

「チューリング完全性」の完全な定義には、無限のメモリが必要です。

有限 (100 ワードまたは 16 ビットまたは 32 ビットなど) のアドレス空間によって制限されることを除いて、完全に使用できるように見えるプログラミング言語および実装について、Turing Complete よりも適切な用語はありますか?

Answer 1

限られたメモリを定義に取り入れることができると思います。何かのようなもの

特定のアーキテクチャ（！）のプログラミング言語は、すべてのチューリングマシンに次のいずれかのプログラムが存在する場合、限定的にチューリング完全です。

a）チューリングマシンをシミュレートし、同じ結果を返します（チューリングマシンが戻った場合）または

b）ある時点で、少なくとも1つの使用可能な限られたリソース（メモリなど）を完全に使用し、任意の結果を返します。

問題は、この直感的な定義が本当に役立つかどうか、またはアーキテクチャに無制限のメモリがあると想定する方がよいかどうかです（実際には有限ですが）。制限されたチューリング完全性（上記で定義）を満たすために一生懸命努力する必要さえないことに注意してください。毎回1バイトをmallocする無限ループに入るだけで、すべてのチューリングマシン用のプログラムが見つかります。

問題は、実装固有のプロパティを固定できないことのようです。たとえば、500KのRAMがある場合、計算するプログラムを表現できる1+1かもしれませんが、そうではないかもしれません。

HaskellやBrainfuckのような言語（はい、私は真剣です）は、リソースを抽象化するため、実際にはチューリング完全であると私は主張します。C ++のような言語は限定的にチューリング完全ですが、ある時点でポインタのアドレス空間が使い果たされ、それ以上のデータをアドレス指定できなくなるためです（たとえば、2 ^ 2 ^ 2 ^ 2 ^ 100アイテムのリストを並べ替えます）。

Answer 2

真に完全なチューリングを実装するには無限のメモリが必要であると言えますが、言語自体にはメモリ制限の概念はありません。言語を変更せずに、100 万ビット マシンまたは 4 ビット マシン用のコンパイラを作成できます。