通用程序的实现

计算理论导引作业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的个数。