计算理论导引作业2020/7/9日交。
1. 通用程序的定义
image.png
即：以z,x为输入，将z转换成程序（指令），去处理x形成的图灵机的带，最后输出y。
2. 通用程序伪码表示
TO E IF ～PROG(Z)
v=1
I=1
A
TO G IF (I=0) ∨(I>Lt(Z))
TO R IF r((Z) I )=1
TO L IF r((Z) I )=2
TO F IF r((Z) I )=3
TO B IF r((Z) I )=4
TO T IF R(r((Z) I , 2) =1
TO C IF (X) V =2
D
I=I+1
TO A
C
W=[(r((Z) I )-3)/2]
I= MIN t≤Lt(Z) L((Z) t ) =W
TO A
T
TO C IF (X) V =1
TO D
B
TO D IF (X) V =1
X=[X/P V ]
TO D
F
TO D IF (X) V =2
X=X·P V { 算术运算}
TO D
L
TO M IF V≠1
X=2*X {Gödel 乘}
TO D
M
V=V-1
TO D
R
TO S IF V ≠ Lt(X)
X=X*2 {Gödel 乘}
S
V=V+1
TO D
G
Y=#(2 ，X) －1
3. 通用程序的实现
注：结合前面的30个程序的实现。
#include <iostream>
#include <vector>
#include <Cmath>
using namespace std;
//定义cantor矩阵查询规模
#define NUM 10
unsigned int aCantor[NUM][NUM];
//求余
unsigned int R(unsigned long long int x, unsigned long long int y) {
unsigned int res;
res = (x % y);
return res;
}
//求x - y
unsigned long long int sub(unsigned long long int x, unsigned long long int y) {
unsigned long long int res;
if (x >= y)
res = x - y;
else
res = 0;
return res;
}
//求反
unsigned int alpha(unsigned long long int x) {
unsigned int res;
res = sub(1, x);
return res;
}
//y可以整除x
unsigned int ycanx(unsigned long long int x, unsigned long long int y) {
unsigned int res;
for (int i = 0; i <= x; i++) {
if (i * y == x) {
res = 0;
break;
}
else
res = 1;
}
return res;
}
//prim:判断x是否是素数（0：是；1：否）
unsigned int prim(unsigned long long int x) {
unsigned int res = 0;
if (x <= 1)
res = 1;
else {
for (int t = 2; t < x; t++) {
res += alpha(ycanx(x, t));
}
res = alpha(alpha(res));
}
return res;
}
//p：求第x个素因子
unsigned int p(unsigned long long int x) {
unsigned int res = 0;
int i = 0, j = 1;//第1个素数是2
while (i != x) {
j++;
if (prim(j) == 0) {
i++;
}
}
res = j;
return res;
}
//Lt：x的最大非零指数素因子的序号
unsigned int Lt(unsigned long long int x) {
//cout << "已经入Lt" << endl;
unsigned int res = 0, i = 1, count = 0;
while (x != 1) {//x一直对素数相除
if (x % p(i) == 0) {//如果可以被这个素数整除
while (x % p(i) == 0) {//就一直整除下去
x = x / p(i);
}
res = i;
}
i++;
}
//cout << "已经退出Lt" << endl;
return res;
}
//an(x)：求得x的哥德尔数
vector<unsigned int> an(unsigned long long int x) {
vector<unsigned int> res;
unsigned int i = 1;//注意第一个素数才是2，不是第0个
while (x != 1) {//x一直对素数相除
unsigned int count = 0;
if (x % p(i) == 0) {//如果可以被这个素数整除
while (x % p(i) == 0) {//就一直整除下去
x = x / p(i);
count++;
//cout << "验证x:" << x << endl;
}
}
res.push_back(count);
i++;
}
return res;
}
//PROG(x)：求x是否为pt程序
unsigned int PROG(unsigned long long int x) {
unsigned int res = 0;//默认谓词为真
//cout << "验证未计算出an" << endl;
vector<unsigned int> rn = an(x);
//cout << "验证已计算出an" << endl;
vector<unsigned int> in;//存左部
vector<unsigned int> jn;//存右部
vector <unsigned int>::iterator tmp0;
vector <unsigned int>::iterator tmp1;
for (tmp0 = rn.begin(); tmp0 != rn.end(); tmp0++) {
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM - i; j++) {
if (aCantor[i][j] == *tmp0) {
if (j == 0)//如果出现j为0就一定不成立
{
return 1;
}
else {//没有的话就继续执行
in.push_back(i);
jn.push_back(j);
}
}
}
}
}
//已经得到了指令左右部“二维”数组
for (tmp0 = in.begin(); tmp0 == in.end(); tmp0++) {
for (tmp1 = jn.begin(); tmp1 == jn.end(); tmp1++) {
//如果两者都不为0
if (in[*tmp0] != 0 && in[*tmp1] != 0) {
if (in[*tmp0] == in[*tmp1]) {//两者相等
return 1;
}
}
}
}
return res;
}
//给定x,y给出对应位置数
unsigned int match(unsigned int x, unsigned int y) {
unsigned int res = 0;
return res = aCantor[x][y];
}
//求指令zi的右部
unsigned int r(unsigned int z) {
//cout << "已经入r" << endl;
unsigned int res = 0;
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM - i; j++) {
if (match(i, j) == z)
res = j;
}
}
return res;
}
//求指令zi的左部
unsigned int l(unsigned int z) {
//cout << "已经入l" << endl;
unsigned int res = 0;
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM - i; j++) {
if (match(i, j) == z)
res = i;
}
}
return res;
}
//哥德尔乘
vector<unsigned int> XGodelY(vector<unsigned int> X, vector<unsigned int> Y) {
vector<unsigned int> res;
vector <unsigned int>::iterator tmp;
for (tmp = Y.begin(); tmp != Y.end(); tmp++) {
X.push_back(*tmp);
}
//a.insert(a.end(), b, begin(), b.end());其实用insert更好
return res = X;
}
//x哥德尔数的第i个
unsigned int xi(unsigned long long int x, unsigned int i) {
unsigned int res = 0, j = 1, count = 0;
if (i >= 0) {
while (x != 1) {//x一直对素数相除
if (x % p(j) == 0) {//如果可以被这个素数整除
while (x % p(j) == 0) {//就一直整除下去
x = x / p(j);
if (j == i)
count++;
}
}
j++;
}
res = count;
}
else
res = 0;
return res;
}
//给出哥德尔数，求整数
unsigned long long int XZ(vector<unsigned int> x_vector) {
unsigned long long int res = 1;
unsigned int i = 1;
vector <unsigned int>::iterator tmp;
for (tmp = x_vector.begin(); tmp != x_vector.end(); tmp++) {
res *= pow(p(i), *tmp);
i++;
}
return res;
}
//求x的素因子分解式中指数为a的个数
unsigned int sharpax(unsigned long long int x, unsigned int a) {
cout << "已经入sharpx" << endl;
unsigned int res = 0;
cout << "进入an" << endl;
vector<unsigned int> anRes = an(x);
cout << "完成an" << endl;
vector <unsigned int>::iterator tmp;
for (tmp = anRes.begin(); tmp != anRes.end(); tmp++) {
if (*tmp == a)
res++;
}
return res;
}
//通用程序
int program() {
//输入数据
int x, y, w, t, choice;
unsigned long long int z;
cout << "请输入z 和 x" << endl;
cin >> z >> x;
//一个vector只存储一个2，用于计算X的哥德尔
vector<unsigned int> xG2;
xG2.push_back(2);
//cout << "xG2输入完毕！" << endl;
//将x放到带上，并计算出它的哥德尔数
vector<unsigned int> x_Godel;
for (int x_i = 0; x_i <= x; x_i++) {
x_Godel.push_back(2); //输入1(godel为2)
}
x_Godel.push_back(1); //最后要输入B(godel为1)，可加可不加
//cout << "tape(x)输入完毕！" << endl;
//通过tape(x)哥德尔数，求出X
unsigned long long int X = XZ(x_Godel);
//cout << "tape(x)转换成X输入完毕！" << endl;
//创造cantor矩阵
int cantor_count0 = 0, cantor_count1 = 0;
int cantor_i = 0, cantor_j = 0;
for (cantor_count0 = 0; cantor_count0 < NUM; cantor_count0++) {
for (cantor_j = 0; cantor_j <= cantor_count0; cantor_j++) {
cantor_i = cantor_count0 - cantor_j;
aCantor[cantor_i][cantor_j] = cantor_count1++;
//验证cantor矩阵的正确性
//cout << cantor_i << " " << cantor_j << endl;
//cout << aCantor[cantor_i][cantor_j] << endl;;
}
}
//cout << "cantor输入完毕！" << endl;
//输出z哥德尔数对一个的cantor矩阵的位置，用于检验
cout << "z在cantor矩阵中对应的编码为：" << endl;
for (int i = 1; i <= Lt(z); i++) {
cout << "Z(" << i << ") = " << xi(z, i) << endl;
cout << "<" << l(xi(z, i)) << ", " << r(xi(z, i)) << ">" << endl;
}
//输出tape(x)
cout << "tape(x) = ";
vector <unsigned int>::iterator tmp;
for (tmp = x_Godel.begin(); tmp != x_Godel.end(); tmp++) {
cout << *tmp << " ";
}
cout << endl;
//输出哥德尔数X
cout << "X = " << X << endl;
//第一步，验证z是否是某一pt程序的哥德尔数
if (PROG(z) == 1) {//如果不是
cout << "z不是某pt程序的哥德尔数！" << endl;
return 0;//就返回
}
else {//如果是
int v = 1, I = 1; //初始化带计数器，指令计数器
//cout << "v，I输入完毕！" << endl;
A:
cout << "已进入A！" << endl;
if (I == 0 || I > Lt(z))
goto G;
else if (r(xi(z, I)) == 1)
goto R;//右移
else if (r(xi(z, I)) == 2)
goto L;//左移
else if (r(xi(z, I)) == 3)
goto F;//写1
else if (r(xi(z, I)) == 4)
goto B;//写B
else if (R(r(xi(z, I)), 2) == 1)
goto T;
else if (xi(X, v) == 2)//指向1
goto C;
D:
cout << "已进入D！" << endl;
I = I + 1;
goto A;
C:
cout << "已进入C！" << endl;
w = (r(xi(z, I)) - 3) / 2;
for (t = 1; t <= Lt(z); t++)
if (l(xi(z, t) == w)) {
I = t;//跳转
break;
}
goto A;
T:
cout << "已进入T！" << endl;
if (xi(X, v) == 1)
goto C;
goto D;
B:
cout << "已进入B！" << endl;
if (xi(X, v) == 1)
goto D;
X = X / p(v);
goto D;
F:
cout << "已进入F！" << endl;
if (xi(X, v) == 2)//如果带上这格是1
goto D;
X = X * p(v);//不是的话就写1
goto D;
L:
cout << "已进入L！" << endl;
if (v != 1)
goto M;
x_Godel = XGodelY(xG2, x_Godel);
X = XZ(x_Godel);
goto D;
M:
cout << "已进入M！" << endl;
v = v - 1;
goto D;
R:
cout << "已进入R！" << endl;
if (v != Lt(X))
goto S;
x_Godel = XGodelY(x_Godel, xG2);
S:
cout << "已进入S！" << endl;
v = v + 1;
goto D;
G:
cout << "已进入G！" << endl;
y = sharpax(X, 2) - 1;
}
cout << "y = " << y << endl;
}
int main()
{
int choice = 1;//选项
while (choice == 1) {
program();
cout << endl;
cout << "1：继续输入；0：终止程序！" << endl;
cin >> choice;
cout << endl;
}
getchar();
return 0;
}
4. 测试实例
image.png
z实现右移一位write 1的操作，将改变0转化成的带上的1的个数。
