Halting Problem Blog

Hi All, and Welcome back to my blog.

You have probably been wondering what I have been doing lately. Well, I have been going over old notes. Trying to figure out which older programs I should finish now that I have time, but I am having a surprising lack of motivation right now. Almost as if my progress has halted.

Ironically, this blog post is probably one of my oldest blog posts as sections of this have been written in 2020 or before. Definitely before I even created a blog account on Medium.

In Computer Science, there is a little problem that is kind of interesting and challenging should you attempt what I am going to describe. Well this may not be challenging to those who have written compilers or parsers correctly, but I really struggle with that.

The problem is called THE HALTING PROBLEM. I say that you need to know how to write compilers and parse languages quite well for you not to struggle with this kind of problem.

What is the HALTING PROBLEM?

The HALTING PROBLEM is basically just a question: “Will the given program always run through to completion (aka halt)?” This means that looking at all of the loops in the given program file or sets of files, it asks: will it halt? But it goes further than just asking if a certain program will halt. It asks “Can I tell if this program will always halt at COMPILE TIME? If so, does the given program halt?” We are are trying to prevent a programmer from running something that would crash their machine.

It is important to note, that servers are built to run infinite loops.

So not all infinite loops are bad. Most are, so whatever the results of a program to detect infinite loops, it should be statistic information, and probably should generate warnings, not necessarily compiler errors.

WHO IS THIS FOR?

Have you ever tried running something, and got frustrated when your IDE crashed? Not only that, but have you ever spent a lot of time trying to figure out what happened and why it crashed? If your IDE crashed, there was a good chance you just lost all of the output and all of the results, not to mention the stack trace that may or may not have included a StackOverFlowError.

If so, you are not alone. Any half cocked programmer, has probably unintentionally created an infinite loop at some point.

Why is this difficult?

Not exactly math, but some parts of math can be applied here. Here is one for Computer Science. It is simply called an Infinite Loop Detector that works 100%(?) of the time. In Computer Science this is called The Halting Problem. It is basically trying to answer this question: Will the program always run through to completion (aka will it halt)? Why this is considered a fool’s errand in math is simply because according to the Halting Problem it cannot be done. Now, they say you cannot do it outright. It is true, it is impossible to make a program that works 100% of the time and is correct 100% of the time for that.

WHY BOTHER TRYING AT ALL? AND OTHER EXAMPLES.

However, you can detect some simple ones likes:

while(true);//do nothing

which can be caught at compile time. Believe it or not, I would like to write a program to do this. But like I said detecting when a method is making enough progress is almost, if not, impossible to do; but if it can be done, congratulations, you detected an infinite loop (IN THE CASE WHERE IT WAS NOT MAKING ENOUGH PROGRESS OR MAKING IT AND THEN UNDOING IT).

In math, we can use limits to determine if something converges or diverges. If it converges, the program is said to run through to completion. If it diverges, the program contains an infinite loop (detected).

Newton’s Root Finder mathematically sometimes diverges and never finds the correct answer if given a starting point that is too far away from the root.

Now Operating Systems developers say that they have developed such a thing as deadlock-avoidance code (most of them simply do not acknowledge the deadlocks). But the fact that there is such a thing, means that it is possible to detect the deadlock (a deadlock is another form of an Infinite Loop where A waits on B waits on C … waits on A forever, OR A waits on B waits on A forever, OR A waits on A forever).

So I am arguing that some Infinite Loops can be detected while others cannot which is a stance somewhat against The Halting Problem. I am saying that we should detect what we can detect at compile time and that program should be written.

WHAT THE PROGRAM NEEDS AND SOME ASSUMPTIONS:

We can search for known loops and functions on known files. However, this assumes that other files not given, will be treated as always completes which may or may not be true (but since the program has nothing to test, it cannot argue against the assumption either, so always make sure to include all known files that need testing).

We can build a function call map (or if we are dealing with deadlocks we can build a Resource Allocation Graph RAG which essentially does the same thing). A function map is like a resource map which maps function calls. This could potentially flag where loops are and functions that need further inspection. The calls themselves may vary.

A waits on B waits on C waits on A Infinite Loop Resource Allocation Graph Image

We can use an approach called Structural Analysis. Structural analysis is an approach designed to look at loops, look at the breaking conditions and asks what happens when the loops enter is it possible to exit?

//assume mstr is a non-empty, non-null string
for (let i = 0; i < mstr.length; i--)
{
  //do nothing with i inside the for loop
  //do not have any break statements present at all
}

//the for loop will start at i = 0, then i = -1, ...
//but the string length is a non-zero positive string length integer
//non-zero was required for loop entry.
//so since i is always going to be negative, it will never be positive
//that loop will never end.

If the breaking conditions never ever change under certain conditions, we may have at least one Infinite Loop. If we are always moving always from the breaking condition (above), then we have at least one Infinite Loop.

function factorial(let n)
{
  const num = Number(n);//make sure that n is a number
  if (num === 0 || num === 1) return 1;//0! 0 factorial = 1 and 1! = 1
  else return num * factorial(num - 1);//recursive call note num * (num - 1)!
}

//that is a recursive function which calls itself.
//however what happens when n < 0?
//factorial(-1) => not 0 and not 1 so return -1 * (-2)!
//factorial(-2) => return -2 * (-3)!
//...
//it will never end until the IDE runs out of memory on the call stack
//and crashes with StackOverFlowError.

Think of a factorial program (example code above) with negative numbers that does not error on them, does not reverse the loop to be adding, or does not call it again with absolute value of n, in that case when given n < 0, the loop statement always runs with n — 1, it will decrement forever never approaching 0 because it is always moving away from it. So that is an Infinite Loop. However any positive or zero number will halt it.

If it is inconclusive, we can flag it as such. Basically Structural analysis identifies that the loop always happens and what is needed, so it never ends if such is possible. The goal is to do this independently of the input required for the program (so it can be done at compile time).

Although we cared what the value of n was, we just looked at what values make it loop, and then asked what the values were doing? We saw that if it was 0 or 1, it halted, but otherwise it did (n -1)! So we could ask what values would make the next one keep getting bigger? Anything that is less than 0 because -1-1=-2. The magnitude kept getting bigger. Whereas on the positive side 2–1=1. So that kept getting smaller.

A GENERAL PROCEDURE AND PROGRAM DESIGN:

1. Read in the code. Assume the code compiles beforehand. Read in the code as follows: get java/c++/what_ever_language file from the user or programmatically, then: if you only choose a partial file, set initial line number variable and make sure you have access to every method that you call (if they are from java.lang, assume they always end because 99% of the time if not 100% they will end, unless you are testing that particular code). Make sure there is a way to add more code to the strings list (ArrayList).

Get Christopher Hugh Kelly’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Note the following for each file read in:
A: where the comments are get indexes for each file read in.
B: where all of the methods start and end.
C: where all of the loops start and end.
D: Also note method calls including:
1. For each file read in, we note which method comes from which class. Read the method look for the . then get the object look at definition for said object to get the class name from.
2. Next classify the methods if the body has 1 line in it or if it if it has zero lines in the body, between 1 and 10, or more. Zero is no worries. 1 is called pass through/convenience. 1–10 is called minor method. More than 10 is called major.
E: If we have different classes in one file, note if the classes are abstract or an interface or normal.

2. Search for infinite loops. Use the definition of an infinite loop (loops not making any progress, and loops moving away from the ending “break” condition(s)) to check for infinite loops if there is none return 0, if there is at least one return 1, if you cannot tell return 2. Return or throw exception(s).
A: If you never reach condition for loop to end or code will always skip it, return 1/throw the generated exception. Can be determined with constant variables. If code will always end, return 0/don’t throw generated exception. Otherwise if cannot tell with recursive methods (since it isn’t always possible to tell), so return 2.
B: If there are infinite loops, generate a custom runtime exception that lists the method calls and lines that result in the loop and add them to the caused by list. Throw the exception at the end of execution.

3. LOOPS:

There are many kinds of loops:

A: while (true condition) body
is the standard while loop. It does the body if the condition is true and it always checks the condition before each execution.
B: do body while (true condition)
is the standard do while loop. It does the body one time and then checks the condition (repeating until condition is false just like a while loop).

while(true);//do nothing
while(true)
{
  //do something here body of the loop
  //if there are no break statements in this loop, then this is infinite.
}
let a = 1;
while(a < 10)
{
  //do something here
  //if a is never incremented or always decremented
  //then this is infinite.
}

do
{
  //body of loop
  //if this does not change the condition and there are no break statements
  //then this is infinite.
}
while(true);

C: for (variable declaration; true condition; variable progression statement) body
is the standard for loop which creates a variable and declares its scope to be that loop (unless it exists outside of the loop and a new one was not declared) then it checks to see if the condition is true. If condition is true do the body until it is false, but after each execution of the body the variable is progressed with the statement. If continue is reached, the rest of the body is skipped and variable progress statement is executed.
Note: if you say for (var-dec; true; var-progress) body is the same as a while (true) body or do while(true) body.

//assume mstr is a string that is non-null, and non-empty
//so the for loops are entered into
for (let i = 0; i < mstr.length; i++)
{
  //do something here
  //this for loop will end
}
for (let i = 0; true; i++)
{
  //if there are no break statements, then this will be infinite
  //this for loop is equivalent of let i = 0; while(true) i++;
}
for (let i = 0; i < mstr.length; i+=0)
{
  //if the index never increments, or always decrements,
  //then this is infinite
}

D: for(variable type name: collection name) body
is the standard for each loop going over an array or a list or a queue (collection) in forward fashion. The collection if it isn’t an array can be modified during execution (test with infinitely growing list). Thus if you have a for each loop which adds to the collection, then there is the possibility (not sure of this) of it being infinite (unless the adding stops).

E: Iterators are a special type of loop over a list of objects this goes through the objects and will do something to them however, there is no possibility for an infinite loop because the list/array/collection iterated over cannot be modified outside of iterator otherwise an exception will be thrown crashing your code. The exception itself was an indicator of an infinite loop though (the run time environment detected it and instead of executing it, it threw the ConcurrentModification exception).

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ConcurrentModificationExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        for (int n = 0; n < 5; n++) list.add(n+1);//1,2,3,4,5
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer item = iterator.next();
            if (item.equals(2)) list.remove(item);//concurrent modification exception
        }
    }
}

https://www.geeksforgeeks.org/java/concurrentmodificationexception-while-using-iterator-in-java/

ANOTHER EXAMPLE BUT WITH A FOR EACH LOOP:

import java.util.ArrayList;
import java.util.List;
public class ConcurrentModificationExample {
    public static void main(String[] args) {
        List<Integer> sports = new ArrayList<String>();
        sports.add("Tennis");
        sports.add("Basketball");
        sports.add("Swimming");
        sports.add("Golf");
        for (String sport: sports) {//basically means for each sport in sports where the : is in
            if (sport.equals("Basketball")) sports.remove(sport);//concurrent modification exception
        }
    }
}

THE REASON THIS IS THE CASE IS FOR EACH LOOPS ARE BASICALLY ITERATORS. THE COMPILER TURNS THEM INTO ITERATORS AT COMPILE TIME.

HOWEVER TO FIX THIS EXAMPLE, YOU NEED TO USE AN ITERATOR.

F: Recursive methods (suppose you are already on a web page looking up the definition of recursion which simply says: “See recursion (with hyperlink to it)” then you click on it and it takes you back to that page … need I say more. You may also be thinking circular reference.

Special Case: Pass through method that is recursive on accident. Pass through methods have 1 line in the body not including the end.

Well written recursive methods have 3 parts:
1. The base case where the recursion stops.
2. A way to make progress or to stop the recursion.
3. The recursive call(s).

When this is infinite (when a recursive method is an infinite loop), at least #3 is present (the recursive call otherwise the loop would never exist in the first place) but at least one part of the other parts is missing or incomplete. These are more difficult to see and analysis may fail to detect the problem as some are not obvious or structure problems, but rather logic problems with a dependency for instance. The accidental pass through recursion instead is good test case.

G: More than one method calling each other in circular fashion. A calls B then B calls A with the original parameters changing nothing about execution. Can be demonstrated with 2 or more methods. When it is with 1 however this is called Recursion.

 public static int factorial(int n)
 {
   if (num === 0 || num === 1) return 1;//0! 0 factorial = 1 and 1! = 1
   else return num * factorial(num - 1);//recursive call note num * (num - 1)!
 }

 //that is a recursive function which calls itself.
 //however what happens when n < 0?
 //factorial(-1) => not 0 and not 1 so return -1 * (-2)!
 //factorial(-2) => return -2 * (-3)!
 //...
 //it will never end until the IDE runs out of memory on the call stack
 //and crashes with StackOverFlowError. 

 //three methods below demonstrate A calls B calls C calls A
 //can also demonstrate A calls B calls A
 public static void circc() { circa(); }
 public static void circb() { circc(); }
 public static void circa() { circb(); }

 public static void circd() { circe(); }
 public static void circe() { circd(); }
 
 //demonstrates accidentally recursive pass through method
 //ptta(final boolean a) is accidentally recursive pass through
 public static void ptta(final boolean a, final boolean b)
 {
  if (a) return;
  else if (b) return;
  //else;//do something else
 }
 public static void ptta(final boolean a) { ptta(a); }
 public static void ptta() { ptta(true); }

H: Other languages like Python or JS (not JAVA) let you import stuff conditionally. This poses a problem especially when files have not fully loaded. Of course this occurs with 2 or more files trying to import stuff from each other creating a dependency loop with those import statements. For example: File A: has some method and it depends on a method in file B. File B imports File A immediately. Python will throw an error called CircularImport Error. The Error itself is an indicator of an infinite loop. The CircularImport error is a runtime error though it may have been detectable at compile time.

#FILE a.py:
from b import bfunc;
def afunc():
   return "alpha version 1.0";
print(bfunc());

#FILE b.py:
from a import afunc;
def bfunc():
   return "beta version 2.0";
print(afunc());

It fails because it reads the first line in a (which is from b import bfunc).
Then it starts to read b. The first line in b is (from a import afunc).
Since a has not finished loading yet, it crashes at runtime infinite loop.

YOU CAN FIX IT BY:

#FILE a.py:
#from b import bfunc; #notice the import line was removed and added below in a new function
def afunc():
   return "alpha version 1.0";
def printbfunc():
   from b import bfunc;
   print(bfunc());
printbfunc();

#SAME AS ABOVE:
#FILE b.py:
from a import afunc;
def bfunc():
   return "beta version 2.0";
print(afunc());

#OR

#FILE a.py:
import b;#note not a specific function just the whole module
def afunc():
   return "alpha version 1.0";
print(b.bfunc());

#SAME AS ABOVE:
#FILE b.py:
from a import afunc;
def bfunc():
   return "beta version 2.0";
print(afunc());

BUT IF YOU DO SOMETHING LIKE:

#FILE c.py:
import d;
def cfunc():
   print("c display");
d.dfunc();

#FILE d.py:
import c;
def dfunc():
   print("d display");
c.cfunc();

IT WILL CRASH. SO ORDER IN WHICH YOU IMPORT STUFF MATTERS.
https://www.geeksforgeeks.org/python/python-circular-imports/

I: It is worth it to note that a StackOverFlowError exists and indicates that there was infinite loop. However this is a runtime error. The Halting problem specifically states we are not trying to catch these errors at runtime, but at compile time. This error means the program runtime environment ran out of memory. Could be caused by infinite printing or infinite memory allocation (memory allocation also occurs when you call functions because each recursive call gets its own memory space, but it will still have access to variables outside of that function). It could also be caused by an infinite loop doing some calculation storing a lot of data in variables for each call causing the program to run out of memory and crash.

Once you note all the kinds of loops and specific examples of each that can cause problems it becomes a little easier to spot them in code. If a human can do it, then you might be able to write a program to do it. These examples clearly are not all of them because there are infinitely many programming languages, so there are infinitely many programs that have these infinite loops. But if you ignore comments, and variable names more or less, and only focus on the structure and the consequences of entering said loops (IE structural analysis, look at the source code and see what obvious problems exist), it becomes pretty easy to see some infinite loops. It also becomes obvious why it is very hard if not impossible to write an Infinite Loop Detector.

This reminds me when I was learning Lisp or RaketLang in Principles of Programming Languages when I was in college. I looked at some code, and realized that the code was an infinite loop. Because it would run the recursive code, but there was no way for it to make progress. So I was the only one in the room who told the teacher not to run it. He ran it anywasy and then had to force the program to end via the Task Manager.

Thanks for reading, everyone. Maybe I have inspired you to take on writing some sort of program like that. If you do, I hope this blog has been a good guide for you.