計算の基本要素
計算を基本要素に分解していき、計算の本質を探る
データは文字列の
0,1 のみ演算は文字列型の基本演算
制御構造は
if 、 while のみ↑のような基本要素のみを持ったプログラムを「標準形プログラム」と言うなら、
任意の多項式時間計算可能関数は、それを計算する標準形プログラムが存在する
データの基本要素
集合\Sigma=\{0,1\}さえあれば、全てのデータを表現できる
実際、バイナリがそうだしな
文字列型
\Sigma上の文字列型を\Sigma^\astと表す
0 、 1 を数値ではなく、文字列の記号として扱うという意味\Sigmaでない一般の文字列\Gammaの文字列に関しても、コード化できれば\Sigmaの2進列で表現可能
数値型
2進数で表現できる
1進表記でも表現できる
ex. \underline{2}_{10}= \underline{00}_1、\underline{4}_{10}= \underline{0000}_1とすればいい
整数型
こういうrecordを考える
tstype N = {
sign: Σ, // 0==`-`, 1==`+`
abs: Σ^* // 2進数
}recordはみやすさのために導入しているだけであって、本質ではない
ex.
-12 → {sign: 0, abs: 1100} レコードを使わない場合は、以下のタプルを使って
[0,1100] と表現タプル、配列型
\Sigmaである
0 , 1 を表すために3bit使えば表現力が上がる対応表
| 表現したいもの | Σ上の記号 |
| 0 | 000 |
| 1 | 111 |
| [ | 100 |
| , | 010 |
| ] | 001 |
ex.
[10,11] → 100111000010111111001 この表現方法を使えば、任意の要素数の配列も、入れ子の配列も表現可能
ただ、bitの使い方が富豪なので、めちゃくちゃ長くなる
上の例の場合だと桁数は3(\sum^n_{i=1}|a_i|+n+1)になる
\sum+1の部分でカンマと両括弧分
Pascalにnullっぽい
ε というのがあるのかな [1,ε,0] のときなどは、εはガン無視で 100 111 010 010 000 001 と表す論理値
対応表
| true | 1 |
| false | 0 |
論理記号
ルールを定めれば\Sigma^*で表現できる
\lorは
0011 など当たり前すぎるが
以上の議論を加味すれば、プログラミング言語で書かれたコードそのものも、逐次的に\Sigma^*に変換できる
print を p は 1000111 、 r は 1000110 のように変換する(値は適当)制御構造の基本要素
primitiveには
if と while があれば全て表現可能関数定義と関数呼び出し
if と while で表現可能 if/while のみで表現するまでの変換手順これを変換する
a.tsLoop: {
if x==null then halt(1);
a = head(x);
x = right(x);
if a==1 then halt(0) else goto Loop;
}1. プログラムを
if/goto のみに変換する関数呼び出しを全てインライン展開するなどする
再帰関数は最後までインライン展開できないがこれはスタックを利用すると良いらしい
意味がわからん
そもそも最後までインライン展開できないのか？
各行をラベル付けし、
if/goto のみで遷移できるように書き換えるb.tsL1: if x==null then goto L5 else goto L2;
L2: a=head(x); goto L3;
L3: x=right(x); goto L4;
L4: if a==1 then goto L6 else goto L1;
L5: c=1; goto L0;
L6: c=0; goto L0;
L0: halt(c);2. whileで全体を囲いgotoの代わりにswitchを使う
switchはifに変換可能
c.tspc=1;
while pc != o {
switch pc
case 1: if x==null then pc=5 else pc=2;
case 2: a=head(x); pc=3;
case 3: x=right(x); pc=4;
case 4: if a==1 then pc=6; pc=1;
case 5: c=1; pc=0;
case 6: c=0; pc=0;
}参考