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)

One thought on “A question for a course in Advanced Geek Meditation.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: