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. 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.

I read Laws of Form, and I don't see that my arguments are anywhere in the book at all. The truth value provides a comprehensive solution to all the major paradoxes and to Cantor's diagonal argument, and it says something interesting about the halting problem. The reason I am convinced my arguments are new is that I have talked with a large number of professors at multiple universities about the truth value, or at least told them what the truth value is, and none of them have ever heard of the truth value in any of these problems. My problem now is just that I don't know how to get my results public.

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. "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 ): 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.

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.

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.

There are positive and negative sorts of infinite recursion in my article. I'm not sure if this is what you are thinking of, but you have given me a lot of ideas, so thank you very much! There are statements that are true if they are false and false if they are true, like "This statement is false". In Russell's paradox, [math]P \in P[/math] is true if it is false and false if it is true. There are other statements that are true if they are true and false if they are false, like "This statement is true". The infinite recursion looks different in these two types of statements. Most of the statements in my article fit these two forms, but the crocodile dilemma does not. I was originally making a distinction between them and having two versions of the truth value, but because of the crocodile dilemma I have just been having a single truth value. I will add some to my article to discuss the distinction now, though. Thanks for the ideas! I think people generally regard statements that are true if they are false and false if they are true as contradictions. I am saying we want to rephrase the expression. We should say the statement "This statement is false" or [math]P \in P[/math] is true if it holds that it is false and false if it holds that it is true. Phrased this way, the expression is not a contradiction but instead infinite recursion. When we ask if the statement is true or false, we have to find out if it holds that the statement is true or false. Now the statements just have the single truth value, the recursive truth value, instead of two different truth values at the same time. They are true if they are false and false if they are true. However, they are neither true nor false. They are not true, so we cannot conclude they are false. They are not false, so we cannot conclude they are true. They are not contradictions. I think people usually don't regard "This statement is true" or the set of all sets that are members of themselves as problematic? They really are. "This statement is true" is true if it holds that it is true and false if it holds that it is false. So when we ask if it is true or false, we have to ask if it is true or false. I didn't include the set of all sets that are members of themselves in the PDF on Russell's paradox I attached to my first post, but it is in my article in the section on Russell's paradox: We ask if [math]P^\prime[/math] is a member of itself. It is a member of itself if it is a member of itself. So we have to ask if it is a member of itself. [math]P^\prime \in P^\prime[/math] is true if it holds that it is true and false if it holds that it is false. Have you seen this argument for this set before? If anyone here knows of any more statements than those in my article that are true if they are false and false if they are true, or the other way around, you might want to consider if they have this truth value. Let me know about it if you do know of any more. Oh, thanks so much for talking with me. I really appreciate it.

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.

I chose the wrong focus for my post. What I would really like the most from posting on these forums and what would make me very happy would be if people could make progress on the halting problem based on what I have in my article. I found the truth value in a problem related to the halting problem, and it is also in Cantor's diagonal argument. I posted about the halting problem in the computer science forum at http://www.scienceforums.net/topic/79883-can-you-make-progress-on-the-halting-problem-based-on-this/ . Are people aware that this truth value is also in Cantor's diagonal argument, the Grelling-Nelson paradox, the crocodile dilemma, and Berry's paradox? I ordered a copy of "Laws of Form" and am looking forward to reading it. Well, I don't know if people here thought my arguments for the liar paradox or Russell's paradox are correct in the first place. Some of my friends think they are correct. I just think that any time anyone discusses the liar paradox or Russell's paradox, they should give these solutions. "This statement is true", "This statement is false", and [math]P \in P[/math] are neither true nor false but instead have this truth value. It is just the behavior of these statements when we ask if they are true or false. I think these solutions should be in the Wikipedia articles on the liar paradox and Russell's paradox for one matter, but they are not there. Thank you again for your responses. Yes, there is the version of the liar paradox with two statements, but I think we would say of the version "This statement is false" that it is just a single statement? Then I'm sorry, but I still don't know what you mean by this line: "100 If you have not reached this line end program." It is supposed to be a line in a computer program? It seems to me that if the program reaches this line, all that happens is that the "end program" statement is not executed, but I'm sure I am not understanding what you mean. I was able to find the truth value in Russell's paradox because I first found it it two really strange sets I discovered: [math]A = \{x \: | \: x \in A\}[/math] [math]B = \{x \: | \: x \not\in B\}[/math] They are the sets A and B. Something is an element of A if it is an element of A. Something is an element of B if it is not an element of B. B is very similar to the set in Russell's paradox. Have you seen these sets before? I think they are actually very funny. They are at the beginning of my article. I can explain them more here if you like.

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: 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

Thank you for the reference, then. I shall have to read "Laws of Form" in more detail. So I'm clear, do you think my arguments for the liar paradox and Russell's paradox are correct? You are just saying people already know about them?

Thank you very much for your responses. I really appreciate it. I have read some of "Laws of Form". I may not be remembering correctly, or I may not have gotten far enough into the book, but I don't remember him talking about infinite recursion with these problems or, when we ask if a statement is true or false, asking if it is true or false over and over again. Does he talk about that? Oh, I'm sorry, studiot, I'm not quite sure what you mean. What do you mean by the liar paradox containing two statements?

Hello everyone, I have found that a certain strange truth value, different from true and false, appears in all of 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. I am certainly not an expert in these problems, but I have not seen my arguments anywhere else. I think that my arguments might be new and that they say something important about these problems. I would really like to see what you think. My article is on my web page as "The Infinitely Recursive Truth Value" at http://www4.ncsu.edu/~tjarmst3/ . I am hoping some people here will be willing to discuss it. I enrolled in a computer science Ph.D. program this fall, but there are not any professors at my university who will discuss this project or my Semantic Web project. So I am still on my own finding people with whom to discuss it. I describe the truth value in my article like this: Do you think that's interesting? I have one formal and two informal arguments on the liar paradox. Here is my one informal argument: Do you think that's correct? Have you seen that before? Then I wanted to show you my argument for Russell's paradox too. I couldn't get all the LaTeX to come out right in the forum, so I am attaching a PDF. So, it is exactly the same behavior in both the liar paradox and Russell's paradox. When we ask if a statement is true or false, we keep asking if it is true or false over and over, forever. Another problem in my article is Cantor's diagonal argument, but it is a bit long to explain in a post here. I came up with a certain way of formalizing the diagonal and anti-diagonal as sets in which the truth value appear and in which we actually can include the anti-diagonal as a row in the matrix. I also came up with something about the halting problem that I think is very interesting. So, thank you so much if you have any comments! Tim Armstrong http://www4.ncsu.edu/~tjarmst3/ Russells_paradox.pdf