Computability Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// A minimal Turing-complete flavor: a register machine with simple instructions.
5
// Instructions:
6
//  - INC r              : R[r]++
7
//  - DECJZ r, label     : if R[r]==0 jump to label; else R[r]-- and fallthrough
8
//  - JUMP label         : unconditional jump
9
//  - WRITE1             : set an output flag (semantic property we will use)
10
//  - HALT               : stop execution
11
// Labels are resolved to instruction indices before running.
12
13
struct Instr {
14
    enum Op { INC, DECJZ, JUMP, WRITE1, HALT } op;
15
    int r = -1;                  // register index (if any)
16
    string label;                // label target (if any)
17
};
18
19
struct Program {
20
    vector<pair<string, Instr>> code; // optional label on each instruction
21
};
22
23
struct Executable {
24
    vector<Instr> code;                 // flattened code with labels resolved
25
    unordered_map<string,int> labelPos; // label -> pc index
26
};
27
28
Executable assemble(const Program& P) {
29
    Executable E;
30
    // First pass: record positions of labels
31
    int pc = 0;
32
    for (auto& li : P.code) {
33
        const string& lab = li.first;
34
        if (!lab.empty()) {
35
            if (E.labelPos.count(lab)) throw runtime_error("Duplicate label: "+lab);
36
            E.labelPos[lab] = pc;
37
        }
38
        pc++;
39
    }
40
    // Second pass: emit instructions with resolved labels later
41
    for (auto& li : P.code) E.code.push_back(li.second);
42
    return E;
43
}
44
45
struct RunResult {
46
    bool halted = false;
47
    bool wrote1 = false;  // whether WRITE1 executed at least once
48
    long long steps = 0;  // steps executed
49
};
50
51
RunResult run(const Executable& E, long long maxSteps = LLONG_MAX, size_t regCount = 4) {
52
    vector<long long> R(regCount, 0); // finite set of registers (extend as needed)
53
    long long steps = 0;
54
    bool wrote1 = false;
55
    long long pc = 0;
56
    auto getTarget = [&](const string& lab)->long long {
57
        auto it = E.labelPos.find(lab);
58
        if (it == E.labelPos.end()) throw runtime_error("Unknown label: "+lab);
59
        return it->second;
60
    };
61
    while (pc >= 0 && pc < (long long)E.code.size() && steps < maxSteps) {
62
        const Instr& ins = E.code[pc];
63
        steps++;
64
        switch (ins.op) {
65
            case Instr::INC:
66
                if ((size_t)ins.r >= R.size()) R.resize(ins.r+1, 0);
67
                R[ins.r]++;
68
                pc++;
69
                break;
70
            case Instr::DECJZ:
71
                if ((size_t)ins.r >= R.size()) R.resize(ins.r+1, 0);
72
                if (R[ins.r] == 0) {
73
                    pc = getTarget(ins.label);
74
                } else {
75
                    R[ins.r]--;
76
                    pc++;
77
                }
78
                break;
79
            case Instr::JUMP:
80
                pc = getTarget(ins.label);
81
                break;
82
            case Instr::WRITE1:
83
                wrote1 = true;
84
                pc++;
85
                break;
86
            case Instr::HALT:
87
                return {true, wrote1, steps};
88
        }
89
    }
90
    // Timed out or fell off code (treat fall-off as HALT)
91
    bool halted = (pc < 0 || pc >= (long long)E.code.size());
92
    return {halted, wrote1, steps};
93
}
94
95
// Build a program conveniently
96
Program makeProgram(initializer_list<pair<string, Instr>> lst) {
97
    Program P; P.code.assign(lst.begin(), lst.end());
98
    return P;
99
}
100
101
// Reduction constructor: Given a program P, produce P' that runs P then, if it halts,
102
// executes WRITE1 and HALT. If P diverges, control never reaches the appended code.
103
Program appendWrite1OnHalt(const Program& P) {
104
    Program P2 = P;
105
    // Add a fresh label for the appended code
106
    P2.code.push_back({"__APPEND_START__", Instr{Instr::WRITE1, -1, ""}});
107
    P2.code.push_back({"", Instr{Instr::HALT, -1, ""}});
108
    return P2;
109
}
110
111
int main() {
112
    // Example 1: A halting program that increments R0 twice then halts.
113
    Program HaltProg = makeProgram({
114
        {"", Instr{Instr::INC, 0, ""}},
115
        {"", Instr{Instr::INC, 0, ""}},
116
        {"", Instr{Instr::HALT, -1, ""}}
117
    });
118
119
    // Example 2: A non-halting (looping) program: L: INC R0; JUMP L
120
    Program LoopProg = makeProgram({
121
        {"L", Instr{Instr::INC, 0, ""}},
122
        {"",  Instr{Instr::JUMP, -1, "L"}}
123
    });
124
125
    Executable EH = assemble(HaltProg);
126
    Executable EL = assemble(LoopProg);
127
128
    // Run with a generous step limit
129
    auto rH = run(EH, 1000);
130
    auto rL = run(EL, 1000); // will time out without halting
131
132
    cout << "HaltProg: halted=" << rH.halted << ", wrote1=" << rH.wrote1 << ", steps=" << rH.steps << "\n";
133
    cout << "LoopProg: halted=" << rL.halted << ", wrote1=" << rL.wrote1 << ", steps=" << rL.steps << "\n";
134
135
    // Demonstrate a mapping reduction idea: transform P -> P' that writes 1 iff P halts.
136
    Program HaltProgPrime = appendWrite1OnHalt(HaltProg);
137
    Program LoopProgPrime = appendWrite1OnHalt(LoopProg);
138
139
    auto rH2 = run(assemble(HaltProgPrime), 1000);
140
    auto rL2 = run(assemble(LoopProgPrime), 1000);
141
142
    cout << "HaltProg': halted=" << rH2.halted << ", wrote1=" << rH2.wrote1 << " (should be true)\n";
143
    cout << "LoopProg': halted=" << rL2.halted << ", wrote1=" << rL2.wrote1 << " (should be false within time bound)\n";
144
145
    return 0;
146
}
147

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Instr { enum Op { INC, DECJZ, JUMP, WRITE1, HALT } op; int r=-1; string label; };
5
struct Program { vector<pair<string, Instr>> code; };
6
struct Executable { vector<Instr> code; unordered_map<string,int> labelPos; };
7
8
Executable assemble(const Program& P){ Executable E; int pc=0; for(auto& li:P.code){ if(!li.first.empty()){ if(E.labelPos.count(li.first)) throw runtime_error("dup label"); E.labelPos[li.first]=pc; } pc++; } for(auto& li:P.code) E.code.push_back(li.second); return E; }
9
10
struct RunResult{ bool halted=false; long long steps=0; };
11
RunResult run(const Executable& E, long long maxSteps=LLONG_MAX, size_t regCount=4){ vector<long long> R(regCount,0); long long pc=0,steps=0; auto L=[&](const string& s){auto it=E.labelPos.find(s); if(it==E.labelPos.end()) throw runtime_error("bad label"); return it->second;}; while(pc>=0 && pc<(long long)E.code.size() && steps<maxSteps){ const Instr& ins=E.code[pc]; steps++; switch(ins.op){ case Instr::INC: if((size_t)ins.r>=R.size()) R.resize(ins.r+1,0); R[ins.r]++; pc++; break; case Instr::DECJZ: if((size_t)ins.r>=R.size()) R.resize(ins.r+1,0); if(R[ins.r]==0) pc=L(ins.label); else { R[ins.r]--; pc++; } break; case Instr::JUMP: pc=L(ins.label); break; case Instr::WRITE1: pc++; break; case Instr::HALT: return {true,steps}; } } bool halted=(pc<0 || pc>=(long long)E.code.size()); return {halted,steps}; }
12
13
Program makeProgram(initializer_list<pair<string, Instr>> lst){ Program P; P.code.assign(lst.begin(),lst.end()); return P; }
14
15
int main(){
16
    // Two programs: one halts, one loops
17
    Program HaltProg = makeProgram({{"", Instr{Instr::INC,0,""}}, {"", Instr{Instr::HALT,-1,""}}});
18
    Program LoopProg = makeProgram({{"L", Instr{Instr::INC,0,""}}, {"", Instr{Instr::JUMP,-1,"L"}}});
19
    vector<Executable> progs = { assemble(HaltProg), assemble(LoopProg) };
20
21
    int N = (int)progs.size();
22
    vector<bool> reported(N,false);
23
24
    // Dovetail: for time bound T=1..MAXT, run each program from scratch for T steps
25
    const int MAXT = 2000; // increase for more coverage
26
    for(int T=1; T<=MAXT; ++T){
27
        for(int i=0;i<N;++i){
28
            if(reported[i]) continue; // already known halting
29
            RunResult r = run(progs[i], T);
30
            if(r.halted){
31
                reported[i] = true;
32
                cout << "Program #" << i << " halts (witnessed within " << T << " steps)\n";
33
            }
34
        }
35
    }
36
    // Any program not reported by now may still halt later; we simply haven't found it yet.
37
    for(int i=0;i<N;++i){ if(!reported[i]) cout << "Program #"<<i<<" not known to halt within bound\n"; }
38
    return 0;
39
}
40