A question for a course in Advanced Geek Meditation.

Even novice programmers can tell that this piece of code will go into an infinite loop, so therefore it will never halt.

def my_infinite_loop() {
    while(true) {
        print("I am running.")
    }
}

---

Can we write a generalized function to see if some arbitrary piece of code halts?

def halts(program) {
    # Something happens here that determines
    # if the code in program halts or not.
    # If the code halts, then this function
    # returns True. If it does not, then this
    # function returns False.
}

For example, if we pass the function “my_infinite_loop” to halts, it should return False. In the example below, one would expect to see the print out: “It does not halt.”

if halts(my_infitite_loop) {
    print("It halts.")
} else {
    print("It does not halt.")
}

Suppose we call the function “halts” inside another piece of code, such as the function g below.

def g(program) {
    if (halts(program)) {
        while(true) {
            print("The program you submitted to me does halt.")
        }
        return True
    } else {
        print("the program you submitted to me does not halt.") 
        return False
    }
}

---

But, now try calling g recursively. What happens? Does it halt? Does it print a report that says it halts?

g(g)