Golang, the Halting Problem, and the Beauty of Unsolvable Questions

What if we could write a Go function that tells us whether another function will run forever?

This question has a beauty to it.

As a programmer, I like the control. I like to design the system that behaves predictably. I reason about the inputs and the outputs. So it feels natural to ask:

Can we build a program that predicts the behavior of another program?

For example: Can we detect the infinite loop?

Lets try this with Golang. Here is the harmless looking function.

func Infinite() {
  for {
  }
}

Now imagine we want to write

func Halts(program func()) bool

This Halts function will return true if the program will run forever and false if it will finish or halt.

At first glance, this feels doable. After all, Go gives us goroutines, channels, timeouts. We’re not powerless.

But in 1936, long before Go existed, Alan Turing proved something astonishing:

No algorithm can universally determine whether another program halts.

This is known as the Halting problem.

What The Halting Problem Actually Says

Given:

• Any program P
• Any input I

Is there a function Halts(P, I) that can always correctly answer:

• true → if P(I) eventually stops
• false → if P(I) runs forever

Turing proved: such a function cannot exist.

This isn’t about Go. It isn’t about syntax. It isn’t about hardware limitations. It’s about the fundamental limits of computation itself.

Before diving into theory, though, let’s try to cheat.

Attempt by using timeout

In Go, we might write something like this:

func Halts(program func(), timeout time.Duration) bool {
	done := make(chan bool)

	go func() {
		program()
		done <- true
	}()

	select {
	case <-done:
		return true
	case <-time.After(timeout):
		return false
	}
}

We launch the program in the goroutine and wait for it to finish or timeout. If it finishes, we say it halts and return true. If it times out, we say it runs forever and return false.

But this is not solution but the guess, what if The program halts but after whatever timeout we set?

The Paradox.

The real magic of Turing’s proof is self-reference.

Suppose our function is perfect and always returns true if the program halts and false if it runs forever.

func Halts(program func()) bool

and we have this program:

func Paradox(program func()) {
    if Halts(program) {
        for {} // loop forever
    }
}

Now what happens if we call:

Paradox(Paradox)

Lets reason about this:

• Case 1: Halts(Paradox) returns true That means Paradox halts. But inside the Paradox if Halts(program) is true it will loop forever. Which is a contradiction.

• Case 2: Halts(Paradox) returns false That means Paradox runs forever. But inside the Paradox if Halts(program) is false the loop will skipped and Paradox will halt. Which is another contradiction.

So no matter what Halts returns, it will be wrong, only conclusion can be function like Halts cannot exist.

And this is what I like about the programming, we can even encode the paradoxes.

Closing the loop

I started with simple question

Can I write a Go function that detects infinite loops?

We can do approximate by doing something like timeout. But answer is no. Not because Golang is weak or I am not smart enough. But structure of logic itself forbids it.

And I find that beautiful.