computer-science - 「計算空間」という用語の意味は何ですか?

Question

「計算空間」という用語の意味は何ですか?

ウィキペディアで、「計算時間」という用語の非常に明確な説明を見つけることができました。すなわち、決定論的チューリングマシン M が入力 x で必要とする時間は、マシンが停止して答え (「はい」または「いいえ」) を出力する前に実行する状態遷移またはステップの総数です。しかし、「計算空間」の同様に明確な定義を見つけることができませんでした。

Answer 1

定義は、あなたが参照した同じ記事で与えられました。ここで、スペースはストレージの場所の数 (またはメモリの量) であるため、言葉遣いを使用してください。

入力 x で決定論的チューリング マシン M が必要とするスペースは、マシンが停止して答え (「はい」または「いいえ」) を出力する前に必要な格納場所またはメモリの総数です。

これが、ウィキペディアの記事で彼らがそれを（空間または時間）と表現した理由です。

スペース要件についても同様の定義を行うことができます。時間と空間は最もよく知られている複雑さのリソースですが、複雑さの尺度はすべて計算リソースと見なすことができます。

Answer 2

n計算スペースは、アルゴリズムを実行するために必要なメモリの量を示します (計算時間と同様に、入力のサイズで表されます)。

Answer 3

ネット上で何かを見つけました（詳細については参照してください）： -http： //www.mozart-oz.org/documentation/tutorial/node12.html

計算スペースは、一般に、計算ストアと実行中のスレッドのセットで構成されます。これまで見てきたのは、単一の計算スペースです。論理プログラミングを扱う場合、複数のネストされた計算スペースを使用すると、より複雑な構造が発生します。計算空間の構造に関する一般的な規則は次のとおりです。

これは、各プロセスがメモリにロードされ、それらの境界が非常に明確に定義されていることを意味します。このようなプロセススペースを取得し、メモリに毎回プログラムをロードすることが難しいのは、ホエイスレッドが発明された理由の1つです。

各スレッドには、（スタック）や共通領域（スレッドが作成されるプロセススペース）などの共通の処理スペースがあるため、適切なスレッド通信を定義する必要があります。