[笔记]GOTO-Programme中的定理及其证明

2018-12-29 本文已影响0人小良OvO

Theorem 1

Jedes GOTO-Programm kann durch ein WHILE-Programm mit nur einer "echten" WHILE-Schleife simuliert werden.

Insbesondere ist also jede GOTO-berechenbare Funktion auch WHILE-berechenbar.

每个GOTO-Programm可以通过一个WHILE-Programm来模拟。这个WHILE-Programm只有一个“真的”WHILE循环。“真的”的意思是，这个WHILE循环是一个“Normalform”，通过证明我们可以看出来：

证明：

WHILE $x_{i} \neq 0$ DO P END

相当于

$M_{1}$ ：IF $x_{i} = 0$ THEN GOTO $M_{2}$ ；P；GOTO $M_{1}$ ;

$M_{2}$ ：HALT

每个GOTO可计算函数都是WHILE可计算的。

证明如下：

假设GOTO-Programm为 $P=M_{1}:A_{1};...;M_{k}:A_{k}$ , $N$ 为一个在P中使用的变量的最大编号。

用IF-THEN结构（这是一个典型的LOOP循环）来表示WHILE-Programm：

$x_{N+1} :=1;$

$WHILE$ $x_{N+1} \neq 0$ $DO$

$IF$ $x_{N+1} =1$ $THEN$ $A_{1}$ '

...

$IF$ $x_{N+1} =k$ $THEN$ $A_{k}$ '

$END$

作为补充，我们可以观察一下 $A_{i}$ 的不同情况：

1. $x_{j}:=x_{i}\pm c$

~> $x_{j}:=x_{i}\pm c;$

$x_{N+1}:=x_{N+1}+1$

2.GOTO $M_{j}$ ~> $x_{N+1}:=j$

3.HALT~> $x_{N+1}:=0$

4.IF $x_{j}=c$ THEN GOTO $M_{n}$

~> $x_{N+1}:=x_{N+1}+1;$

IF $x_{j} = c$ THEN GOTO $x_{N+1}=n$

Theorem 2

Jede Turing-berechenbare Funktion ist GOTO-berechenbar.

每个图灵可计算的函数都是GOTO可计算的。

证明：

给出一个图灵机 $M=（Z,\Sigma ,\Gamma ,\delta ,z_{1},blanksymbol,E）$ ，其中 $\Gamma =\left\{ a_{1},...,a_{m} \right\}$ , $Z=\left\{ z_{1},...,z_{k} \right\}$ 。

观察一个序列 $a_{i_{1}}...a_{i_{p}} z_{l}a_{k_{1}}...a_{j_{q}}$ 其中 $z_{l} \in Z$ , $a_{i_{1}}...a_{i_{p}},a_{k_{1}}...a_{j_{q}} \in I^*$ ，把这个序列改写成 $x,y,z$ 三个数，Basis $b:=m+1$ 。

举例解释以上的x，y，z分别代表什么：

$\Gamma =\left\{ a_{1},a_{2} \right\}$ ，那么 $m=2$ ， $b=m+1=3$ 。

序列 $a_{1}a_{2} z_{l}a_{2}a_{1}a_{1}$ ，则 $z:=l$ , $x:=<a_{1}a_{2}>=(1,2)_{3}=1\cdot 3^1+2 \cdot 3^0=5$ , $y:=<a_{2}a_{1}a_{1}>=(1,1,2)_{3}=2\cdot 3^0+1 \cdot 3^1+1\cdot 3^2=14$

$x:=\sum\nolimits_{\mu =1}^p i_{\mu}b^{p-\mu}=(i_{1}...i_{p})_b$

$y:=\sum\nolimits_{\mu =0}^{q-1} j_{\mu+1}b^{\mu}=(j_{q}...j_{1})_b$ 。和x不一样，y是倒过来的。

$z:=l$ ，为状态的下标编号。

用GOTO-Programm来表示的话只有以下的四种形式：

$M_{1}:P_{1};$ 从起始序列生成x，y，z（LOOP可计算）

$M_{2}:P_{2};$ M的模拟

$M_{3}:P_{3};$ 把给出的 $x_{0}$ 翻译回 $y$ （LOOP可计算）

$HALT$

$P_{1}$ 和 $P_{3}$ 包括了数学运算，所以是LOOP可计算的。需要考虑的是 $P_{2}$ 。关于 $P_{2}$ 用以下的例子来解释：

现在的序列是 $a_{i_{1}}...a_{i_{p}} z_{l}a_{k_{1}}...a_{j_{q}}$ ，并且 $\delta (z_{l},a_{j_{1}})=(z_{l*},a_{j_{r}},L)$

所以x，y，z就有了相应的改变。这些改变可以用GOTO-Programm来模拟。y和z的改变中需要用到MOD和DIV，这两个操作也是LOOP可计算的。需要去掉最后一位的时候用DIV b，需要增加最后一位的时候要先乘上b，需要取最后一位则用MOD b。当最后 $z_{i} \in E$ 的时候则 $IF$ $z=i$ $THEN$ $GOTO$ $M_{3}$ 。

[笔记]GOTO-Programme中的定理及其证明

猜你喜欢

热点阅读