Thread: Halting problem

  1. #1
    Registered User
    Join Date
    Apr 2017
    Posts
    5

    Halting problem

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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170
    Well it's an unreadable single line.

    Try again, and preview before you post.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2017
    Posts
    5

    Dont know why it left out new lines

    Quote Originally Posted by Salem View Post
    Well it's an unreadable single line.

    Try again, and preview before you post.
    Code:
    #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;
    }

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Even when it's not all on one line it doesn't really make any more sense
    Code:
    #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;
    }

  5. #5
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    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.

  6. #6
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    "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.

  7. #7
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    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.
    Last edited by Newberry; 05-04-2017 at 03:52 PM.

  8. #8
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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?

  9. #9
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,731
    I guess they're trying to show with code how the halting problem is impossible to solve.
    Devoted my life to programming...

  10. #10
    Registered User
    Join Date
    Apr 2017
    Posts
    5
    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.

  11. #11
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,731
    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:
    Code:
    int myFunction(int);
    you don't know its implementation. Can you ever say "No, it doesn't halt."?
    Last edited by GReaper; 05-05-2017 at 05:27 AM.
    Devoted my life to programming...

  12. #12
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    @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?

  13. #13
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    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.
    Last edited by MacNilly; 05-13-2017 at 09:05 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-09-2014, 06:46 PM
  2. Problem passing argument into function, basic problem
    By tsdad in forum C++ Programming
    Replies: 7
    Last Post: 05-22-2013, 12:09 PM
  3. Replies: 1
    Last Post: 12-07-2012, 10:00 AM
  4. Dialog box halting program
    By george7378 in forum Windows Programming
    Replies: 9
    Last Post: 07-21-2011, 02:53 AM
  5. Halting execution
    By rickyoswaldiow in forum C++ Programming
    Replies: 1
    Last Post: 10-19-2006, 07:10 AM

Tags for this Thread