Halting problem

[Newberry]

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.

   #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;   }

[Salem]

Well it's an unreadable single line.

Try again, and preview before you post.

[Newberry]

Well it's an unreadable single line.

Try again, and preview before you post.

#include <stdio.h>

#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;
}

[algorism]

Even when it's not all on one line it doesn't really make any more sense

#include <stdio.h>

#define DEPTH (1000)

static int level = 0;
unsigned int s, k;

A(unsigned int n, unsigned int m);

int checkStack(void) {
    level++;    
    if (level >= DEPTH){
        printf("Almost got there. Have run out of stack.\n\n");
        level--;
        return 1;
    }
    return 0;
}

void C_k(unsigned int n) {
    A(n,n);
}

void C_s() {
    C_k(s);
}

// If A(n,m) halts then C_n(m) does NOT halt.
void 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(void) {
    level = 0;
    k = (unsigned int)C_k;
    s = (unsigned int)C_s;
    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;
}

[Newberry]

C_s() is the equivalent of SELF-HALT(SELF-HALT) in Alex's article "The Halting Problem." I would not necessarily try to translate one into the other as it may confuse things. Suffices to say that A(n,m) is a program such that when it halts then C_n(m) does not halt. C_s() is a self-contradictory, self-referential program defined by means of A(). If A() is consistent then C_s() does NOT halt, but A() does not know it. I am nevertheless saying that A() can know that C_k(s) does NOT halt.

[algorism]

"I would not necessarily try to translate one into the other as it may confuse things." Go for it. Believe me, it couldn't be any more confusing. Translate it into the terms of the article you are referencing. When you share your code with other humanoids, you need to try to make it readable instead of peppering it with a bunch of meaningless names.

[Newberry]

I am proposing to use Roger Penrose’s notation (Penrose, R., 1994, Shadows of the Mind, pp. 73-75) because he managed to simplify the matter even further. I realize that thinking that people will be generally familiar with it is an unwarranted assumption. But trust me – it will enable to deal with the issue more effectively. If I have time I will post the relevant passages from his book on-line. In the meantime just a brief explanation.

A(n,m) is like DOES-HALT(program,program), but it does not tell us when a program does halt. It only tells us when it does NOT – by halting. I.e. if A(n,m) halts then C_n(m) does NOT halt. The equivalences are roughly

DOES-HALT(n,m) ~ A(n,m)
SELF-HALT(n) ~ C_k(n)
SELF-HALT(SELF-HALT) ~ C_s()

C_s() is attempting to say that it itself does not halt. But it can’t. The moment it halts it would contradict itself.

BTW, thanks for restoring my code. I do not know why I had trouble with posting it. But the dots were there for a reason.

[algorism]

What is the purpose of your code? It seems idiotic and meaningless to me.
Are you telling us that you've made some sort of breakthrough in understanding this problem?

[GReaper]

I guess they're trying to show with code how the halting problem is impossible to solve.

[Newberry]

I am showing that A(k,s) halts without any contradiction, i.e. A() can make the decision that C_k(s) does NOT halt.

[GReaper]

You completely missed the point of the halting problem.

Let's imagine that A is a black box that takes some input and outputs something. How long are you willing to wait for it to provide output until you decide it will never do so? The answer is, you can never decide that, because you can't be sure of what is going on inside it.

In other words, I have a function that does something:

int myFunction(int);

you don't know its implementation. Can you ever say "No, it doesn't halt."?

[algorism]

@GReaper,
He's certainly seems to have missed the point, but it isn't true that the function to be tested would be a black box.

The does_it_halt function is passed the function to be tested (i.e. it's source or object code) and the input to test it with. It then determines if the given function will halt with the given input. It doesn't "run" the function.

The does_it_halt function is proven to be impossible by first assuming that it is possible and then creating a contradictory (impossible) function from it.

@OP,
Please answer this question yes or no: do you think you've made a new discovery?

[MacNilly]

The real heart of the halting "problem" is for people trying to prove that some algorithm they invented always terminates for all inputs. Like those graph and sorting algorithms you've heard of.. proved correct. And also unlike some type-inference algorithms (like ML and Haskell) that are already proved to NOT halt for some programs.


My understanding of the halting problem is:

There cannot (does not) exist a program A which halts if and only if some (*arbitrary*) program B, halts.

How does some program A determine if another program B halts? There is just no way, it's pretty simple. That's because a general computation allows for possibly infinite loops.

There are a lot of strange mathematical proofs of this, but it IS really straightforward ...

Now, program B here was stated to be *arbitrary*. Certainly, for any GIVEN program B, it MIGHT be possible to determine if it halts or not. Then the human would be the program A. But in general, it's just not possible, only by waiting for program B to complete.


Also, the fact that anyone would go to such lengths as to write a program that attempts to "solve" or even demonstrate the halting problem is seriously WTF???
Why do they make such a big deal out of this? Just call it a freaking infinite loop, or "bottom" if you're mathematically inclined.