What is wrong with the code below? This post is a response to the article on the Halting Problem, but it uses Roger Penrose's notation. (Penrose, R., 1994, Shadows of the Mind, pp. 73-75) The point is that we get the answer that C_k(s) does NOT halt without any apparent contradiction.
Code:
#include #define DEPTH (1000) #define INITIALIZE level = 0; k = (unsigned int)C_k; \ s = (unsigned int)C_s; static int level = 0; unsigned int s, k; A(unsigned int n, unsigned int m); // Forward declaration int checkStack(void) { level++; if (level >= DEPTH){ printf("Almost got there. Have run out of stack.\n\n"); level--; return 1; } return 0; } C_k(unsigned int n) { A(n,n); } C_s() { C_k(s); } // If A(n,m) halts then C_n(m) does NOT halt. A(unsigned int n, unsigned int m) { if ( checkStack() ) return; // . . . . . if (n == s) C_s(); // . . . . . if (n == k && m == s) { // Analyze what happens when A() calls C_s() // Does C_s() have a base case? printf("Program C_%u( %u ) does NOT halt.\n\n", n, m); } // . . . . . level--; } int main(int argc, char *argv[]) { INITIALIZE // macro A(k,s); // Does C_k(s) halt? No. C_k(s); // Does C_s() halt? No answer. A(s,0); // Does C_s() halt? No answer. return 0; }