Can you make progress on the halting problem based on this?

[tarmstrong]

Hello everyone,

I posted in the mathematics forum about a strange truth value I found in Russell's paradox, the liar paradox, Cantor's diagonal argument, the Grelling-Nelson paradox, the crocodile dilemma, a problem related to the halting problem I came up with, and Berry's paradox: http://www.scienceforums.net/topic/79642-strange-behavior-in-the-liar-paradox-russells-paradox-cantors-diagonal-argument-and-more-problems/ . I had thought I was saying something new about the liar paradox and Russell's paradox, but maybe what I am saying about those problems is not new. I thought I might have found something new about some of the other problems, though, including the halting problem. My article is on my web page as "The Infinitely Recursive Truth Value" at http://www4.ncsu.edu/~tjarmst3/ .

What I would like most out of posting in these forums and out of writing my article would be if people could make progress on the halting problem based on what I found. I would just be very happy if anyone could. I thought you might be able to!

Here is the truth value I found, repeating from my post in the mathematics forum:

 

Sometimes the only means of finding the truth value of a logical statement, considered in either a natural or formal language, includes finding its truth value as part of the process. For some statements, when we ask if they are true or false, by the nature of the statements we keep asking if they are true or false over and over, infinitely, and never arrive at true or false. As part of the procedure to find the truth value of a statement, we need to find the truth value of the same statement. We write a computer procedure to compute a predicate. When we call the procedure with certain arguments, inside the procedure is a recursive call to the same procedure with exactly the same arguments. The procedure to evaluate the predicate recurses infinitely when we use it to decide if a statement is true or false. To find the truth value of the statement, we have to keep trying to find the truth value of the statement again and again, forever. It is a truth value because some statements are true, other statements are false, and still other statements, when we ask if they are true or false, have this other behavior.

 

This truth value appears in all the related problems I listed. The first problem in which I found it is a problem related to the halting problem I came up with: a predicate that takes as its first argument a program that terminates in finite time under all input, and as its second argument a particular input to that program, and decides if the program running the input would either halt with an answer or throw an exception, as in modern programming languages. So instead of asking whether a program running with a particular input halts with an answer or runs forever, we ask whether it halts with an answer or throws an exception. Of course the program to compute this predicate is trivial. We just run the program with the input and see what happens. The program will either halt with an answer or throw an exception in finite time.

This predicate is similar to the one in the halting problem, and we can treat it in exactly the same way and get the same paradox from it. However, we actually have a trivial program to compute this predicate, and we can just run the program. When we do run the program, we get this strange truth value. When we ask if the program running the input either halts with an answer or throws an exception, we keep asking if it halts with an answer or throws an exception over and over, infinitely. It is really strange behavior! I would really like to see if anyone here can tell if this problem says anything about the halting problem itself. I attached the section in my article on the halting problem to this post as a PDF hoping people would like to read it.

Well, I don't know if the section in my article on Cantor's diagonal argument says anything about the halting problem independently. I came up with a certain way of formalizing the diagonal and anti-diagonal as sets, writing their indicator functions and set definitions, in which the truth value appears. There may be other ways of formalizing them as sets in which the truth value does not appear, but I think these formalizations are straightforward and make a lot of sense. With these formalizations, we actually can include the anti-diagonal as a row in the matrix. We get the truth value on the diagonal when we include both the diagonal and anti-diagonal as rows. All the sections in my article are independent, so you could read any of the sections on their own if you like.

Thank you so much if you have any comments!

halting_problem.pdf

[AtomicMaster]

The halting problem is prety much a problem of finding recursion. The proposed method of "if it ever calls itself with the same value" is quite flawed, and extremely inefficient as you have to keep track of every recursion that happens, which is a lot in an infinitely-recursive program. Postulating that not every infinitely recursive program will ever call itself with the same value, and not every non-infinitely recursive program will call itself with always different values, i don't believe that the proposed method gets us any closer to the solution. Much like judging based on execution times, and instruction patterns.

[tarmstrong]

Thanks so much for responding. Oh, I don't think I have the phrase "if it ever calls itself with the same value" anywhere in my post or article. I do have the phrase "if it ever calls itself with the same argument" in the section of my article "Detecting Infinite Recursion". So I'm not sure if you read that section and if that's what you meant. Are you saying that section is flawed, or are you referring to something else?

Detecting infinite recursion in general is part of the halting problem, but that section in the article just describes how we can detect infinite recursion in the special case that the procedure calls are with exactly the same arguments, which is sufficient for detecting infinite recursion in all the problems in my article.

[AtomicMaster]

I did mistype, and it doesnt change my point.

 

Let me just make sure i understand your par solution to the problem of "by looking at code determine if it will halt or run forever".

 

Does this sound about right:

1 - So you look at code and you generate similar code that is either the same or is some magically-selected part of the code (didn't get that) but that code also throws exceptions

2 - Then you pass it to another piece of code that takes the generated code, and run it inside your wrapper (or sandbox if you will)

3 - Then, because the code is throwing exceptions, and you are able to trace some execution aspects of the original code

4 - That allows you to somehow magically determine that the generated code is infinitely recursive

5 - And because you are running the original code or a magically-selected carcass of the original code, you can make statements about the original code?

[tarmstrong]

The section "Detecting Infinite Recursion" isn't the interesting part of my article and doesn't matter so much to the rest of the article. That's not the section I was hoping would give people ideas about the halting problem.

I thought my argument was clear in that section. All I am saying is that it is straightforward to determine if a program running an input will recurse infinitely in the special case that the recursive calls are with exactly the same arguments as each other. We run the program with the input. As we are running it, we just keep track of all the procedure calls. If the program is ever executing a procedure with certain inputs, and then further executes the same procedure with the same inputs, we know the program has entered infinite recursion. When the program executes the second procedure call, it will run the program in exactly the same manner as it did after the first procedure call. The program will call the procedure with the same arguments a third time, a fourth time, etc., infinitely.

That's all I'm saying in that section. That method is sufficient for detecting infinite recursion in all the problems in my article, but not for detecting infinite recursion in general.

[Sensei]

The program will call the procedure with the same arguments a third time, a fourth time, etc., infinitely.

 

 

You don't need any arguments to function to have not infinite recursion...

 

int count = 100000; // global

 

void f1( void )

{

if( count > 0 )

{

count--;

f1();

}

}

When function is calling other function return address is stored on cpu stack. It has finite size. On Windows stack has default 1 MB size per thread. When stack is filled, application is crashing and is shut down automatically by operating system.

 

So, there is really no problem in modern times.

 

In the beginning of computers, it could be problem to detect whether program is halted or is simply crunching data, without task manager, GUI etc. which allows us now to check what is going on with our application.

Edited November 15, 2013 by Sensei

[AtomicMaster]

I am still in a bit of confusion as to how your paper is supposed to make us be closer to a halting problem solution. If i write a regular expression that will simply look at code and detect a while(1)-type loop, we would be no closer to the solution, even though i just detected a special case where the program would not halt...

 

That's aside from your mistaken assumption that a program or part there-of that ever calls itself with the same argument is infinitely recursive.

[tarmstrong]

In this method of detecting infinite recursion, we need to treat global variables as part of the arguments of all procedures that have access to these variables. Maybe I can make what I am saying clearer. If a program ever executes the same line of code twice with the exact same values of all the variables in the program, we know the program has entered either infinite recursion or an infinite loop. The program will just execute again the same way it did the first time. If the line of code the program executes twice is a procedure call, we know the program has entered infinite recursion. If the line of code it executes twice is a line of code in a loop, we know the program has entered an infinite loop. As I say, this method works only for special cases of infinite recursion and loops. It does not help with the general case where the variables in the program may be different.

 

Well, I think my problem related to the halting problem that I attached as a PDF is interesting, at least. I don’t know if it says anything about the halting problem itself, beyond the suggestions I give at the end of this section. I was hoping people here might be able to say if it says anything about the halting problem itself. What I think is very interesting, though, is what I found about Cantor’s diagonal argument, which may also say something about the halting problem. My understanding of Cantor’s diagonal argument is that it would be very good news, that it would be a very positive result that people would really like, if we actually can include the anti-diagonal as a row in the matrix. That is my conclusion.

Edited November 16, 2013 by tarmstrong

[AtomicMaster]

 

If a program ever executes the same line of code twice with the exact same values of all the variables in the program, we know the program has entered either infinite recursion or an infinite loop.

And i am telling you that this is a poor assumption to make, even with recursion and loops.

 

Examples:

 

Socket, or IPC-based programming will include loops like this all the time:

 

while(1){

if data on socket

read

break

else

sleep

}

 

So this causes a false-positive for infinite loop detection

 

Any sort of more advanced programs will include structures, structures that will be passed to code that may recurse, but here's the kicker, how do you know what changes in those structures are relevant to the recursion? The only thing being passed to the functions will be a pointer...

To the same point: recursive searches or traversals of datastructures will often pass the same value into the search function, and as we shift locations in the tree, we will perform a recursive search(the same data)

 

These would be false-negatives as you keep track of all the variables and values.

 

 

I mean yes, your code will work in very specific cases, but again, so will a /while\s*\([1|true]\)/i

[tarmstrong]

In this method of detecting infinite recursion, if the argument to a procedure is a pointer to a data structure, then we need to treat the whole data structure as part of the arguments to the procedure.

 

I mean yes, your code will work in very specific cases, but again, so will a /while\s*\([1|true]\)/i

 

"Detecting Infinite Recursion" is the least interesting section in my article and isn't at all what I was hoping to discuss. I didn't mean for that section to say anything at all interesting about the halting problem. This method of detecting infinite recursion works for all the problems in my article, which is all I was trying to say in that section.

 

Let me be clearer about what I was hoping to discuss. What my problem related to the halting problem tells us about the halting problem itself is that if the approach we take to the halting problem, to telling if a program running an input would halt, consists of actually running the program with the input inside the procedure to tell if the program halts (halt() in my article), then we get my truth value when running the program people usually present as being problematic for the halting problem, Y() in my article, or in the Wikipedia article on the halting problem ( http://en.wikipedia.org/w/index.php?title=Halting_problem&oldid=582199545 ):

 

procedure compute_g(i):
if f(i,i) == 0 then
return 0
else
loop forever

 

Getting the truth value running this program would be incredibly significant. The way people discuss the halting problem is to run this program with the input of the natural number that represents this program itself. I am calling the number [math]y_0[/math] in my article. You can see what happens. We run Y([math]y_0[/math]). Then inside Y() we run halt([math]y_0, y_0[/math]). Then we run Y([math]y_0[/math]) again inside halt(). Then we run halt([math]y_0, y_0[/math]) again. halt([math]y_0, y_0[/math]) would have my truth value.

My suggestion is that we try to think of a practical way of solving the halting problem that does actually involve running the program with the input. Here is an approach I came up with. I think this approach is very sensible. Unfortunately, this approach involves two complex problems that I don't know how to solve myself, but maybe someone in the world could. There is a complication too.

Consider this approach to telling if a program running an input will either halt, loop infinitely, or recurse infinitely. Run the program with the input and accumulate the values of all the variables in the program until we reach either the beginning of a loop or a procedure call. Consider first the case where we encounter a loop before a procedure call. The complex problem is: if we know the values of all the variables in the program at the beginning of the loop, and the structure of the code of the loop, can we tell if the loop will halt? Having the values of all the variables in the program is certainly valuable information. A way to accumulate the values of the variables is to run the program with the input. If halt() finds the loop will loop infinitely, then halt() returns false. If it detects the loop will halt, then halt() continues running the program through the end of the loop and then looks for the next loop or procedure call.

Then consider the case where we encounter a procedure call before we encounter a loop. We want to know if the procedure will recurse infinitely. The complex problem is: if we know the argument to the procedure call, and the structure of the code of the procedure, can we tell if the procedure is going to recurse infinitely? It might help if we wait until the second call to the procedure and find out what its arguments are too. Knowing the arguments to a procedure call is certainly valuable information for telling if the procedure is going to recurse infinitely. A way to find the arguments to a procedure call is to run the program with the input until we reach the procedure call in the code.

Well, if we take this approach, we run Y([math]y_0[/math]). Then we run halt([math]y_0, y_0[/math]). Then halt() runs Y([math]y_0[/math]). If all halt() does is detect infinite loops and not infinite recursion, then we run halt([math]y_0, y_0[/math]) again to get the value of the condition for entry into the loop before entering it the first time. If halt() also detects infinite recursion, though, it seems halt() finds the procedure call halt([math]y_0, y_0[/math]) before it finds the loop and must determine first if halt([math]y_0, y_0[/math]) will recurse infinitely before it reaches the loop. I wanted to ask you what you think happens here.

Thanks. I thought people here would find all of this interesting.

[Sensei]

In this method of detecting infinite recursion, if the argument to a procedure is a pointer to a data structure, then we need to treat the whole data structure as part of the arguments to the procedure.

 

 

How can you know size of structure that has been passed to function?

You don't have source code.. (do you plan making application which will be analyzing c/c++ source codes to check out whether they have potentially infinite loops ?)

Size of structure might be dynamic. Might be operating system dependent. In early Windows we were using structures called tags, they have structure size as first member of structure. Before using some field we were checking whether data.size >= sizeof( data ) to check out whether structure has enough size (so it's running on XP for instance).

What if structure is constant, but have pointer(s) to other structure that is changed?

What if structure has pointers to pointers to pointers etc. they are all const, but final data (you have no idea how deep) is changing?

What if changing counter is read from disk (or registry, or other hardware), and saved, and never stored in memory.. ?

 

 

This method of detecting infinite recursion works for all the problems in my article, which is all I was trying to say in that section.

 

 

Infinite RECURSION, calling the same function over and over again, is NOT EXISTING problem. As I have already told you. Cpu stack is filled, and program is crashing and stopping working. Automatically. You don't need any program that will analyze it to tell whether it halted or not.

 

Infinite loop, is completely different subject.

 

The main Windows OS loop

while( (bRet = GetMessage( &msg, hWnd, 0, 0 )) != 0){     if (bRet == -1)    {        // handle the error and possibly exit    }    else    {        TranslateMessage(&msg);         DispatchMessage(&msg);     }}

is infinite from point of view of analyzing it automatic program.. It ends only when user clicked close button window or so. But it's inside of operating system! And initiated by user action (which detecting program has no idea about).

 

 

[AtomicMaster]

What my problem related to the halting problem tells us about the halting problem itself is that if the approach we take to the halting problem, to telling if a program running an input would halt, consists of actually running the program with the input inside the procedure to tell if the program halts

...

 

 

My suggestion is that we try to think of a practical way of solving the halting problem that does actually involve running the program with the input.

You can't solve the halting problem "by examining program code, determining if the code halts or runs indefinitely" by running the program. It's like trying to determine what a modern nuclear weapon would do to a city the size of LA by firing an ICBM at LA...

 

 

 

Infinite RECURSION, calling the same function over and over again, is NOT EXISTING problem. As I have already told you. Cpu stack is filled, and program is crashing and stopping working. Automatically. You don't need any program that will analyze it to tell whether it halted or not.

You don't "need" anything, the halting problem solution would however tell you that a program that infinitely recurses, recurses infinitely. Without running it, and without running into a stack issue. And it's not a non-issue, it's a non-undetectable problem due to the limitation of current CPU design. Imagine if we had a CPU that during recursion would never run out of stack, maybe there is no stack there to fill up. Solution to halting needs to work for code, any code...

Edited November 25, 2013 by AtomicMaster

[tarmstrong]

Yes, the halting problem in general needs to be able to determine if a program will recurse infinitely without relying on the stack overflowing to tell us that it is recursing infinitely. We need to distinguish between the cases of the stack overflowing due to infinite recursion on the one hand, and on the other hand the stack overflowing just from insufficient memory for the stack for a program that would halt if it had more memory.

I imagine there would be a lot of practical difficulties in implementing my approach for detecting infinite recursion in "Detecting Infinite Recursion" on real world software systems. It works in simple software systems in which it is possible to treat all variables to which a procedure has read access as part of the arguments to the procedure. Thank you for pointing out the difficulties for implementing the algorithm practically. I will add a line to my article saying this approach will work easily only for simple software systems.

 

You can't solve the halting problem "by examining program code, determining if the code halts or runs indefinitely" by running the program. It's like trying to determine what a modern nuclear weapon would do to a city the size of LA by firing an ICBM at LA...

May I ask what you find bad about this approach? I think running the program with the input is a very sensible approach to telling if the program will halt. What I am giving you here is just the easy part of the algorithm, but it says something interesting about the paradox in the halting problem. It is the paradox that makes the halting problem undecidable and apparently impossible to solve. No one has said anything here about the paradox.

Let me clarify my last post a bit. To tell if the program halts, halt() runs the program with the input. When it encounters a loop, the complex problem is to use the values of the variables at the beginning of the loop and the structure of the code of the loop to tell if the loop will halt (like humans do). If the loop does not halt, halt() returns "false". If the loop does halt, halt() executes the loop and continues running the program. When halt() encounters a procedure call, it runs the procedure until it finds a recursive call to the procedure. Then the complex problem is whether these two procedure calls with known arguments will recurse infinitely. If they do not recurse infinitely, halt() executes the procedure calls to completion, returns from the procedure calls, and continues running the program after the procedure calls. Then the way halt() knows the program does halt is from having run the program with the input through to completion past all the loops and procedure calls.

Don't you think this approach to solving the halting problem is very sensible? I am very interested in what you think it says about the paradox. I was hoping someone in the community here or someone else someone here knows would have ideas about the complex problems. I don't know how to approach these complex problems myself, and I don't even know what books I could read that would help.

I do have many more important problems in my article that I would really value discussing with people, as in my post on the mathematics forum http://www.scienceforums.net/topic/79642-strange-behavior-in-the-liar-paradox-russells-paradox-cantors-diagonal-argument-and-more-problems/ . I have developed full solutions to Russell's paradox, the liar paradox, Cantor's diagonal argument, the Grelling-Nelson paradox, the crocodile dilemma, and Berry's paradox that I am convinced are correct and new. Some of these problems are really fun to read and even sometimes humorous.

Edited November 27, 2013 by tarmstrong

[Sensei]

No one has said anything here about the paradox.

 

 

Because it's computer science section, not philosophy section..

 

If you're interested in talking about philosophy or mathematic, you are in wrong forum.

 

 

Let me clarify my last post a bit. To tell if the program halts, halt() runs the program with the input. When it encounters a loop, the complex problem is to use the values of the variables at the beginning of the loop and the structure of the code of the loop to tell if the loop will halt (like humans do). If the loop does not halt, halt() returns "false". If the loop does halt, halt() executes the loop and continues running the program. When halt() encounters a procedure call, it runs the procedure until it finds a recursive call to the procedure. Then the complex problem is whether these two procedure calls with known arguments will recurse infinitely. If they do not recurse infinitely, halt() executes the procedure calls to completion, returns from the procedure calls, and continues running the program after the procedure calls. Then the way halt() knows the program does halt is from having run the program with the input through to completion past all the loops and procedure calls.

 

 

In 3d ray-tracing, that is recursive, we are using recursion limit. Counter that is increased until it's reaching recursion limit (or reverse, decreasing its value until 0). That's all to get rid of stack overflow that would happen when ray would be fired by mirror surface to other mirror surface that would fire ray to another mirror surface etc.

If you have source code, you don't need any halt() function (which would require making snap shot of entire computer memory, because any cell might be variable), you can (must!) fight against stack overflow using much simpler ways. Simply count how deep routine is, and disallow going any more deeper. Mine the first ray-tracing engine, ended up crashing because of stack overflow, because of infinite recursion, because I forgot implementing recursion limit. Added 3 lines of code (init, increment counter, check if below range), and issue fixed.

 

There are programs which use infinite loops with purpose. Even more often than you think.

It's sometimes used in custom made threads, in multi-thread applications, at the end of their main routine:

 

send signal that thread has finished working

for( ;; ) Sleep( 1000 );

return( 0 ); // never called

}

 

This way thread pointer will still be valid, and the main thread will destroy thread by itself, when it wants.

 

 

And it's not a non-issue, it's a non-undetectable problem due to the limitation of current CPU design. Imagine if we had a CPU that during recursion would never run out of stack, maybe there is no stack there to fill up.

 

 

 

Do CPU without stack exist and are used as the main computer cpu?

It would not have routines, and jsr (jump to subroutine), bsr (branch to subroutine) and rts (return from subroutine) machine instructions.

Some early GPU used by graphics cards don't have routines, and don't have stack.. You can however make infinite loop.

 

If cpu is storing anywhere it's current PC (program counter), then doing jmp [address], then that code is reading previously stored PC, and placing it back in PC. It's hand made stack. And it can have only as big capacity as there is memory available.

 

Operating system can detect simple infinite loop - because such thread is eating whole cpu power.

Edited November 30, 2013 by Sensei