Halting Problem

1
#include <iostream>
2
#include <stdexcept>
3
#include <string>
4
5
// Hypothetical perfect halting oracle (does not actually exist)
6
bool HALT(const std::string& program, const std::string& input) {
7
    // If this could be implemented for all programs and inputs, the Halting Problem
8
    // would be decidable. We deliberately throw to emphasize impossibility.
9
    throw std::logic_error("HALT cannot be implemented in general");
10
}
11
12
// Diagonal program D: given a code/program name P, it asks HALT(P,P).
13
// If HALT says P(P) halts, D loops; otherwise D halts.
14
void D(const std::string& P) {
15
    // Note: we won't actually call HALT, because it can't exist.
16
    // The following reflects the logical definition only.
17
    bool prediction = HALT(P, P); // This line is unimplementable in reality
18
    if (prediction) {
19
        // Infinite loop by design (prevents optimization)
20
        volatile bool keepGoing = true;
21
        while (keepGoing) {}
22
    } else {
23
        return; // Halt immediately
24
    }
25
}
26
27
int main() {
28
    std::cout << "This program illustrates the diagonalization idea.\n";
29
    std::cout << "Assume a perfect HALT(program,input) exists. Define D as: \n";
30
    std::cout << "  if HALT(P,P) == true then loop forever; else halt.\n";
31
    std::cout << "Now ask: what happens if we run D on itself, D(D)?\n";
32
    std::cout << "  - If HALT(D,D) == true, D should loop (contradiction).\n";
33
    std::cout << "  - If HALT(D,D) == false, D should halt (contradiction).\n";
34
    std::cout << "Therefore, HALT cannot exist.\n\n";
35
36
    // We show the impossibility by attempting to call HALT and catching the error.
37
    try {
38
        // The following would be the paradoxical call if HALT existed:
39
        // D("D");
40
        // Instead, we demonstrate that implementing HALT is impossible in general.
41
        bool impossible = HALT("D", "D");
42
        (void)impossible;
43
    } catch (const std::logic_error& e) {
44
        std::cout << "Runtime message: " << e.what() << "\n";
45
    }
46
47
    std::cout << "Conclusion: No general algorithm decides halting for all programs.\n";
48
    return 0;
49
}
50

1
#include <chrono>
2
#include <future>
3
#include <iostream>
4
#include <thread>
5
6
// Run a nullary function f with a time budget. Return true if it finishes within
7
// the budget, false if the time budget expires (meaning "unknown" about halting).
8
// NOTE: This is a heuristic, not a halting decider.
9
template <typename Func>
10
bool halts_within_budget(Func f, std::chrono::milliseconds budget) {
11
    auto fut = std::async(std::launch::async, [f]() {
12
        f();
13
    });
14
    if (fut.wait_for(budget) == std::future_status::ready) {
15
        // Function finished within budget: we can safely say it halts (for this input)
16
        fut.get(); // propagate exceptions if any
17
        return true;
18
    } else {
19
        // Timed out: cannot conclude non-termination. It's just "unknown".
20
        return false;
21
    }
22
}
23
24
void quick_task() {
25
    // A simple terminating computation
26
    volatile long long sum = 0;
27
    for (int i = 0; i < 100000; ++i) sum += i;
28
}
29
30
void slow_but_terminating_task() {
31
    // Sleeps for 200 ms to simulate long work, but it does terminate.
32
    std::this_thread::sleep_for(std::chrono::milliseconds(200));
33
}
34
35
int main() {
36
    using namespace std::chrono;
37
38
    bool a = halts_within_budget(quick_task, milliseconds(50));
39
    bool b = halts_within_budget(slow_but_terminating_task, milliseconds(50));
40
41
    std::cout << "quick_task halts within 50ms? " << (a ? "yes" : "unknown") << "\n";
42
    std::cout << "slow_but_terminating_task halts within 50ms? " << (b ? "yes" : "unknown") << "\n";
43
44
    // If we extend the budget, the slow task will be detected as halting
45
    bool c = halts_within_budget(slow_but_terminating_task, milliseconds(300));
46
    std::cout << "slow_but_terminating_task halts within 300ms? " << (c ? "yes" : "unknown") << "\n";
47
48
    std::cout << "Reminder: timeout says 'unknown' on budget expiry; it never proves non-termination.\n";
49
    return 0;
50
}
51

1
#include <algorithm>
2
#include <iostream>
3
#include <string>
4
5
// Very simple static check for trivial non-terminating loop patterns.
6
// This is NOT a full parser; it only looks for specific substrings like
7
// "while(true)", "for(;;)", or "do { ... } while(true);".
8
bool has_obvious_infinite_loop(const std::string& src) {
9
    auto lower = src;
10
    std::transform(lower.begin(), lower.end(), lower.begin(), [](unsigned char c){ return std::tolower(c); });
11
    if (lower.find("while(true)") != std::string::npos) return true;
12
    if (lower.find("for(;;)") != std::string::npos) return true;
13
    // Handle whitespace-insensitive pattern: while ( true )
14
    // Replace spaces to a compact form for a crude check
15
    std::string compact;
16
    compact.reserve(lower.size());
17
    for (char c : lower) if (!std::isspace(static_cast<unsigned char>(c))) compact.push_back(c);
18
    if (compact.find("while(true)") != std::string::npos) return true;
19
    if (compact.find("do{") != std::string::npos && compact.find("}while(true);") != std::string::npos) return true;
20
    return false;
21
}
22
23
int main() {
24
    const std::string terminating_code = R"CPP(
25
        int sum = 0;
26
        for (int i = 0; i < 10; ++i) sum += i; // terminates
27
    )CPP";
28
29
    const std::string non_terminating_code = R"CPP(
30
        // Trivial infinite loop
31
        while (true) {
32
            // do nothing
33
        }
34
    )CPP";
35
36
    std::cout << "terminating_code has obvious infinite loop? "
37
              << (has_obvious_infinite_loop(terminating_code) ? "yes" : "no") << "\n";
38
    std::cout << "non_terminating_code has obvious infinite loop? "
39
              << (has_obvious_infinite_loop(non_terminating_code) ? "yes" : "no") << "\n";
40
41
    std::cout << "Note: This checker is sound only for the trivial patterns it searches.\n"
42
              << "It is incomplete in general and cannot decide all cases (by Rice's Theorem).\n";
43
    return 0;
44
}
45