2019 年度後期：計算基礎論 (19C5042)

2019 年 10 月 11 日

計算の定義をしてみよう（「計算基礎論」より）
担当：長尾篤樹
概要: この講義では計算の理論を C 言語の一部を用いたプログラム（教科書上では「関数プログラム」と呼んでおり，本講義でもそれに倣う）を用いている．関数プログラムを用いて計算の理論を議論するために必要な準備を今回の授業で行う．

一番大切な定義1

前章で関数とは何かを定義した．関数はある入力に対して，それに対応する出力を持つ．
ここで，ある関数にどのような入力を与えたとしても適切な出力を求められる事を「関数を計算可能である」と呼ぶことにする．その関数の定義域が有限集合である場合は総当たりで対応関係を見る事で計算可能であるので，本講義で扱う関数は定義域が無限集合である場合（例えば，整数全体の集合，{0, 1}∗ 上の列等）想定する．例えば，f (x) = 2x + 1であるとき，関数 f は計算可能であると言える．“計算可能である関数” をより数学的に定義し，その特徴を確認することが本講義の前半の目標となる．そのため，まず一番最初に一番大切な定義から述べる．
定義 1.1 関数が計算可能であるとは，その関数を計算する関数プログラムが存在することである．
この定義の下で以下のような例題を考える事ができる．
例題 1.2 自然数上の 2 変数関数
ここで z は x と y の最小公倍数

least commom multiple(x, y) = z,が計算可能であることを示せ

例題 1.3 自然数上の二つの関数 f, g が以下の条件をみたしているとする．
{0 (g(x) が偶数のとき)
f (x) =1 (g(x) が奇数のとき)
このとき，g が計算可能であるならが f が計算可能であることを示せ
上記二つの例題はまだ解く事ができない．なぜなら「計算する」「関数プログラム」の定義がされていないからである．何かしらを「示す」「証明する」時には，定義から出発1することがほとんどである．「関数プログラム」の定義をどのようにすればよいかを考えるためには，上記二つの例題に対する C 言語プログラムを考えることが重要となる．
1

定義以外にもすでに正しいと示された定理や命題，簡単に確認できる事実や議論をする大本となる公理等を用いることもある．

1

また，本題からすこしズレるが，1.3 が正しいとするとき，その対偶 (contradiction)も正しい．では逆 (conversion) や裏 (Inversion) はどうだろうか．具体的に逆となる命
題や裏となる命題を考えてみてほしい．

自然数，表記の約束

2

前回授業を参照のこと

部分関数

3

関数は定義域が何かしらの集合で示されればよく，N 全体等のよく知られている集合と決めつける必要はない．例えば，以下の例 3.1 に示す関数は N × N 7→ N であるが，定義域は {(x, y) ∈ N2 | y ̸= 0} である．
例 3.1

partial func(x, y) =x+1y

このような明示的に出力をもたない入力が示された定義域を持つ k 変数関数を，を k 変数部分関数と呼ぶ．k 変数部分関数の表記は何通りかあり，たとえば以下のような表記も可能である．
例 3.2{half(x) =x2(x が偶数のとき)定義されない(x が奇数のとき)

また，部分関数を表現する際に関数値対応表を用いる事がある（教科書 7 ページ上部を参照のこと）．
k 変数部分関数 f に対し，⃗n ∈ Nk が定義域に入っているということをf (⃗n) ↓と書き，定義域に入っていないということをf (⃗n) ↑と書く．また，f (⃗n) ↓ も f (⃗n) ↑ も与えられた f と ⃗n に対して当該する場合は True 値を，そうでない場合は False 値を持つこととする（Boolean 値を持つこととする）．これを用いて，k 変数関数 f, g と ⃗n, m⃗ ∈ Nk に対し，f (⃗n) = g(m)⃗ とは，以下の 1., 2. どちらかが2成り立っているものとする．
2

同時には成り立たない．なぜか？

2

1. (f (⃗n) ↓ ∧g(m)⃗ ↓) ∧ (f (⃗n) の値 = g(m)⃗ の値)
2. (f (⃗n) ↑ ∧g(m)⃗ ↑)また，このことから，任意の ⃗n に対して f (⃗n) = g(⃗n) であるとき，f = g と表現する．

4関数プログラム

今回の授業の主題である．関数プログラムは，C 言語プログラムのうち以下の文法や演算子のみをを持つプログラムである．

• 変数の宣言（int 型のみ）
• 代入文 （＝演算子の利用． インクリメントデクリメントも可）• if 文 （else 節も利用可）• while 文（無限ループも可能．ループ中の命令文は空でもよい）• return 文• 整数演算子（+, −, ∗, /, %）（/ は右の値で左の値を割った商を返し，% はその余りを返す）• 比較演算子（==, ! =, < . >, <= . >=）• 論理演算子（&&, ||, !）また，if 文と while 文とを組み合わせることで表現可能な loop 文も別に定義する．ループ
用の変数宣言を外で行う for 文と同じと思ってよい．
現実の C 言語と異なる点として以下の三つがある．まず，演算子の短絡評価は今回は考えない．すなわち，0 ∗ f (x) とあっても f (x) の計算は必ず行い，0! = 0&&g(y, z) とあっても g(y, z) の計算は必ず行う．さらに，メモリやビット長の制限は設けない．すなわち，26 4 以上の整数値も取り扱う事ができる．最後に，実行時エラーや警告のうち以下のモノは値を返すようにする．宣言のみで初期化や代入が行われていない変数を評価した値は0，return 文を用いずに関数が終了してしまった場合の関数の返り値も 0，0 で割った商
も 0，0 で割った余りは割られる数．
関数の再帰的利用は可能とする．上述の文法や演算子以外の標準的な C 言語の機能は用いない．for 文等は用いる文法を組み合わせる事で表現でき，goto 文も書き変え可である．また，計算プログラムは入力と出力とが定められた状態で用いられるため，入出力機構やエラー処理等は必要がない．
以上を用い，以下のように関数プログラムを定義する．
定義 4.1 (関数プログラム，k 入力プログラム) 4 章で示された機能を持つプログラム（を示す文字列）を関数プログラムと呼ぶ．さらに，関数プログラムへの入力が k 個である
とき，それを明示して k 変数関数プログラム，または k 入力プログラムと呼ぶ．

3

計算の定義5

定義 4.1 を元に，以下のように計算 (computation) を定義する．
定義 5.1 (計算) k を自然数，P を k 入力プログラム3 ，f を自然数上の k 変数部分関数4とする．P が f を計算するとは，任意の自然数列 (n1 , n2 , . . . , nk ) に対し，以下が成り立つことである．

• f (n1 , n2 , . . . , nk ) ↓ であるならば，P の入力変数に n1 , n2 , . . . , nk の値を与えて P の実行を開始すると，f (n1 , n2 , . . . , nk に等しい値を返り値として出力し実行が終了する．
• f (n1 , n2 , . . . , nk ) ↑ であるならば，P の入力変数に n1 , n2 , . . . , nk の値を与えて P の実行を開始すると実行は終了せず永遠に止まらない（P の外部からは永遠に止まらないかどうかは判断ができない）．
ここで「計算する」「計算プログラム，k 入力プログラム」の定義が行われたので，計算可能性の定義をもう一度確認する．
定義 5.2 (計算可能性) 自然数上の k 変数関数 f に対しそれを計算する k 入力プログラムが存在するとき，f は計算可能であるという．そのような k 入力プログラムが存在しない
とき，f は計算不可能であるという．
これを用い，例題 1.2,1.3 を解く事が可能となる．さらに，定義 5.1,5.2 より，以下の定理が導かれる．
定理 5.3 自然数上の部分関数 f が計算可能ならば，k を計算する関数プログラムが無数に存在する．
証明は構成的手法で可能である．

34

k 入力プログラムは文字の列で表現されるので大文字で示した
つまり，f :Nk 7→ N4