計算可能性（読み）けいさんかのうせい（その他表記）computability

改訂新版　世界大百科事典

計算可能性 (けいさんかのうせい)
computability

A.M.チューリングとE.L.ポストはほとんど同時に次のような思考上の計算機械を考えた（1936）。正方形にくぎられた無限に長いテープ，内部状態q₀，q₁……，q_iおよび記号s₁，……，s_jとが与えられている。各正方形には一つの記号s_aが印刷されているか空白（s₀で表す）である。各瞬間において機械はちょうど一つの正方形（すなわちs_a）を内部状態q_cで着目している。このとき，テープ上の全印刷，s_aおよびq_cの三つの組を状況といい，とくにc＝1のとき入力，c＝0のとき出力という。c≠0のとき，機械は（s_a，q_c）によって定まる動作（s_aをs_bに変え，一つ右の（左の，または同じ）正方形を内部状態q_dで着目する）を行って次の瞬間の状況へと移る。s_a，q_cを引数とし，動作s_bRq_d（s_bLq_dまたはs_bCq_d）を内容とするi行i＋1列の表が与えられたとき，チューリング機械は定義されたという。自然数nはテープ上でn＋1個の引き続くs₁の列とその左右に1個ずつの空白s₀を用いて表現される。同様に自然数の有限個の組も表現できるが，その際，隣り合った二つの自然数の表現の間には一つのs₀で共有させる。機械Mが自然数の関数f（x₁，……，x_n）を計算するとは次のように定義される。任意のx₁，……，x_nに対して，テープ上でのその表現（その他は全部空白）の最後のs₁を着目しているという状況が入力として与えられたとき機械Mは作動し，f（x₁，……，x_n）＝xのときかつそのときに限って，x₁，……，x_n，xを印刷して，xの表現の最後のs₁を着目しているという状況を出力として停止する。fを計算する機械Mが存在するとき，fは計算可能という。計算可能な関数は帰納的関数と同等な概念である。もともと計算のアルゴリズムとか有限的手法によって計算可能とかいった概念は多分に哲学的なものだが，チャーチA.Churchは，これによって計算可能性の数学的定義としようと提言した。計算可能性はコンピューターの基礎概念をなしているのみならず，数学における決定問題の否定的解決の手段として用いられる重要な概念である。
執筆者：柘植 利之

出典　株式会社平凡社「改訂新版　世界大百科事典」

世界大百科事典（旧版）内の計算可能性の言及

【チューリング機械】より

…以前に書いた記号は参照できるし，消して新しいものと書き換えてもよい。その後の計算可能性の理論や現代のコンピューターの発展を見ても，このチューリングの抽象化は正しかったといえる。他方，チューリングの時代に計算可能性に関していくつかの数学的提案があったが，これらはすべてチューリング機械と同等であることが証明された。…

※「計算可能性」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」