計算理論（その01/X） - 「大人の教養・知識・気付き」を伸ばすブログ

はじめに

Introduction to the Theory of Computation

作者:Sipser, Michael
Course Technology Inc

Amazon

を参照しつつ計算理論を学んでいきます。

はじめに
0.　序章
次回

0.　序章

0.1　オートマトン、計算可能性および複雑性

　本書は「オートマトン、計算可能性および複雑性」を扱う。これらは以下の問いに結びついている：

コンピュータの根本的な可能性と限界とは何か？

オートマトン、計算可能性および複雑性の各領域において、この質問はそれぞれ異なる解釈がなされる。

	領域	内容
(1)	オートマトン	計算の数理モデルが持つ定義や性質を扱う。
(2)	計算可能性	計算問題が解決可能か否かを類別する。
(3)	複雑性	計算が困難であるまたは容易であるかを決定づけるものは何かを議論する。

0.2　数学的用法

　以降、基礎的な数学的用法を扱う(以降、ここでは一般的な高校・大学数学で扱う範囲の議論は省略し、一般的な数学における用語と言い回しが異なったり、新しい概念、以降のために確認した方が良いもののみ扱う。)。

0.2.1　タプル

オブジェクトの数列はある順序で並んだオブジェクトのリストである。以降では数列を

$\begin{aligned} (7,21,57) \end{aligned}$

と括弧「"()"」で囲うことで表現することにする。数列では順番に意味があるため、 $(7,21,57)$ と $(21,7,57)$ は異なるものとして扱う*1。
　数列は無限の場合と有限の場合がある。有限の場合を特にタプルということがある。
　 $A,B$ を2つの集合とするとき、 $A$ と $B$ の $\mathrm{Descartes}$ 積 $A\times B$ *2はその第一成分が $A$ に、その第二成分が $B$ に属するような順序を持ったすべての組み合わせをいう。

0.2.2　述語

　関数の中でもその値域が $\mathrm{TRUE},\mathrm{FALSE}$ のいずれかしか取り得ないものを述語( $\mathrm{predicate}$ $,\ \mathrm{property}$ )という*3。たとえば入力した自然数が偶数ならば真、そうでなければ偽と返す関数 $even$ は述語である。
　その定義域が $k$ 次タプル $A\times A\times\cdots\times A$ であるような述語を関係(relation)*4、特に $k$ 項関係という。

　関数として書く代わりに述語と集合をまとめて表記する方がより便利な場合がある。述語 $P:\mathcal{D}\rightarrow\{\mathrm{TRUE},\mathrm{FALSE}\}$ は $(P,S)$ と書かれることがある。ここで $S=\{a\in D| P(a)=\mathrm{TRUE}\}$ である。

　特別な二項関係として同値関係(equivalence relation)がある。これは2つのオブジェクトが何らかの特徴の観点で同等である(equal)ことを捉える概念である。二項関係 $R$ が同値関係であるとは $R$ が以下の性質を持つことをいう：

$R$ は反射律を満たす： ${}^{\forall}x(xRx)$
$R$ は対称律を満たす： ${}^{\forall}x,{}^{\forall}y\left(xRy=yRx\right)$
$R$ は推移律を満たす： ${}^{\forall}x,{}^{\forall}y,{}^{\forall}z\left(xRy,yRz\Rightarrow xRz\right)$

0.2.3　グラフ

　無向グラフ*5はその一部*6が線で連結した点の集合である。グラフ理論では点はノード(node)や頂点(vertex)と呼ばれ、線はエッジ(枝・辺)と呼ばれる。
　ある特定のノードが持つエッジの数を次数(degree)という。任意の2つのノード間には1つの辺までしか許されない。状況によってはループと呼ばれる、自分へのノードを許す場合もある。

　ノード $i,j$ を含むグラフ $G$ において組み合わせ $(i,j)$ は $i,j$ を連結する枝を表す。無向グラフでは $i,j$ の順序は重要ではなく、そのため $(i,j)$ と $(j,i)$ は同じ枝を表す。順序の無い組み合わせを集合の記法 $\{i,j\}$ で無向の枝を表す場合がある。もし $V$ が $G$ のノードの集合、 $E$ が枝の集合だとするならば、 $G=(V,E)$ と書く。グラフは図またはより形式的に特定の $V,E$ により表現することができる。

　グラフは時にデータを表現するのに用いられる。ノードが都市、辺がそれらをつなぐ高速道路を、もしくはノードが人、辺がその間の友好関係を表すことがある。利便性のためにグラフのノードおよび/または辺は、このときラベル付けされたグラフと呼ばれることもある。

　グラフ $G$ のノードが $H$ のノードの部分集合で、 $G$ の辺が対応するノードの $H$ の辺であるとき、 $G$ は $H$ のサブグラフであるという。

　グラフにおけるパス(経路)は枝により結ばれたノードの列である。単純パスはどのノードも2度経由しないパスを表す。もし任意の2つのノードにそれらをつなぐ経路があるならばグラフは連結している(connected)という。パスが同じノードで始まって終えられるならばそのパスを循環(cycle)という。少なくとも3つのノードを持ち最初のノードと最終のノードのみが繰り返すような循環を単純循環という。グラフが木(tree)であるとは、連結しているが単純循環を持たないようなグラフである。

　有向グラフは線の代わりに矢印で表す。ある特定のノードから出て行く矢印の数をそのノードの出次数(outdegree)といい、ある特定のノードに入る矢印の数を入次数(indegree)という。有向グラフにおいてノード $i$ から $j$ へのエッジを組み合わせ $(i,j)$ で表す。有向グラフ $G$ は形式的には $(V,E)$ で書く。ここで $V$ はノードの集合で、 $E$ は辺の集合である。すべての矢印が同じ方向を向いて進んでいるようなパスを有向パスという。有向パスがすべての2つのノードをつないでいるならば有向グラフは強く連結されているという。有向グラフは二項関係を用いるのが簡単な表現方法である。もし $R$ が定義域を $D\times D$ とするような二項関係であるならば、ラベル付けされたグラフ $G=(D,E)$ は $R$ を表す。このとき $E=\{(x,y)|xRy\}$ である。

0.3　文字列(string)と言語

　文字列(strings of characters)はコンピュータ科学において基本的な構成要素である。ここではアルファベットを任意の空でない有限集合だとし、アルファベットの元はアルファベットを表す記号である。通常、アルファベットおよびアルファベットに属する記号を表現するための字体を表すのにそれぞれ $\Sigma, \Gamma$ を用いる。以下がアルファベットの例である：

$\begin{aligned} \Sigma_1&=\{0,1\},\\ \Sigma_2&=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\},\\ \Gamma&=\{0,1,x,y,z\} \end{aligned}$

　あるアルファベットからの文字列(string over an alphabet)はそのアルファベットからの記号からなる有限の数列を指し、普通はお互いに隣り合わせで書き、コンマで区切らない。たとえばアルファベット $\Sigma_1=\{0,1\}$ に対して $01001$ はアルファベット $\Sigma_1$ からの文字列である。 $w$ が $\Sigma_1$ からの文字列であるとき、 $w$ の長さ(length)は $|w|$ と書き、その文字列が含む記号の数を言う。長さが $0$ であるような文字列は空記号といい、 $\mathcal{\varepsilon}$ で表す。文字列 $w$ が長さとして $n$ を持つ場合、 $w$ を $w=w_1w_2\cdots w_n,\ w_i\in\Sigma,\ i=1,2,\cdots,n$ と書くことができる。アルファベット $w$ の逆元を $w^R$ と書くことにすれば、 $w^{R}=w_nw_{n-1}\cdots w_1$ である。またアルファベット $w=w_1w_2\cdots w_n$ に含まれるアルファベット $w_iw_{i+1}\cdots w_j,$ $1\leq i\lt n,i\lt j\leq n$ を部分文字列(substring)という。たとえば $\mathrm{ghi}$ は $\mathrm{abcdefghijk}$ の部分文字列である。

　アルファベット $x=x_1x_2\cdots x_m,\ x_i\in\Sigma,i=1,2,\cdots,m,\$ $y=y_1y_2\cdots y_n,\$ $y_j\in\Sigma,j=1,2,\cdots,n$ に対して $x$ と $y$ の連接 $xy$ を $xy=x_1\cdots x_my_1\cdots y_n$ で定義される。同じ文字列を何度も連結する場合は $x^k$ でそれを表すこととする。

　文字列の辞書式順序は辞書における順序と同じものである。

0.4　ブール代数

　ブール代数は $\mathrm{TRUE},\ \mathrm{FALSE}$ の2値のみから構築された数学的体系である。当初は純粋数学として受容されてきたものの、今やこの体系はデジタル家電やコンピュータデザインにおける基礎と見なされている。ブール代数において $\mathrm{TRUE},\ \mathrm{FALSE}$ はブール値といい、 $0,1$ で表現されることがある。ブール値は2つの可能性がある状況、たとえば高電圧と低電圧が起こり得る導体や真か偽を取り得る命題、 $\mathrm{yes}$ か $\mathrm{no}$ で答え得る質問に用いる。
　ブール値はブール演算子を用いて計算できる。

	否定( $\mathrm{NOT}$ )	$\neg0=1,\neg1=0$
	論理積( $\mathrm{AND}$ )	$1\land0=0,0\land1=0,0\land0=0,1\land1=1$
	論理和( $\mathrm{OR}$ )	$0\land0=0,1\land0=1,0\land1=1,1\land1=1$

　ブール演算子は、より複雑な算術結果を表すのに和や積を用いるように、単純な命題をより複雑なブール表現に結合するのに用いる。たとえば命題 $P$ および命題 $Q$ に対して $P\land Q$ は $P$ かつ $Q$ を意味する。 $P$ の値をその演算の被演算子( $\mathrm{operand}$ )という。
　他のブール演算子が度々現れることもある。排他的論理和 $\mathrm{XOR}$ は、どちらか一方のみが $1$ であるときに $1$ となるような演算子で、 $\oplus$ で表される。また等価( $\mathrm{quality}$ )は両被演算子が同じ値であるときに $1$ を返す演算子で、 $\leftrightarrow$ と書く。最後に実質含意( $\mathrm{implication}$ )は $\rightarrow$ で表され、最初の被演算子が $1$ で2つ目が $0$ であるときのみに $0$ を返す演算子である。

排他的論理和	等価	実質含意
$0\oplus0=0$	$0\leftrightarrow0=1$	$0\rightarrow0=1$
$0\oplus1=1$	$0\leftrightarrow1=0$	$0\rightarrow1=1$
$1\oplus0=1$	$1\leftrightarrow0=0$	$1\rightarrow0=0$
$1\oplus1=0$	$1\leftrightarrow1=1$	$1\rightarrow1=1$

これらの演算子を用いると様々な関係を構築できる。以下の各行は同値である。

$P\lor Q$	⇔	$\neg\left(\neg P\land \neg Q\right)$
$P\rightarrow Q$	⇔	$\neg P\lor Q$
$P\leftrightarrow Q$	⇔	$\left(P\rightarrow Q\right)\land\left(Q\rightarrow P\right)$
$P\oplus Q$	⇔	$\neg\left(P\leftrightarrow Q\right)$