Forever Functional #37 — Can AI do that?

Given the advances in Artificial Intelligence (AI), often coupled with Machine Learning (ML), which have provided us with tools like ChatGPT and others, the question pops up again: Is there anything AI cannot do? Can AI do anything we can think of? This article will consider that question, look at an interesting problem, and see whether AI can handle it.

An old question

Asking if machines could do everything started with Alan Turing, the English mathematician who was key in breaking the German secret codes during World War II, as shown in the movie “The Imitation Game”. Back in 1950 (many years before we had computers even minimally approaching the power and capabilities of modern ones), he wrote a paper, “Computing Machinery and Intelligence”, in which he considered the question, “Can machines think?” The paper is very interesting and defined a test (“Turing’s Test”) by which it could be possible to decide whether machines can be said to think.

In the article, Turing considered nine possible objections and finally decided it was possible that machines could think, but not at that time. The article also discussed what is meant by “thinking”!

If we want to consider that question, it seems that our question, “Can AI do that?” (meaning, anything we can dream of, and in particular thinking) could have a positive answer, though it’s still pending… so we’re left with an incertitude. Let’s consider instead a rather simpler question, whose answer could be a boon to developers, mathematicians, logicians, and more!

A simpler (?) question

Instead of thinking about machines being able to do any task requiring intelligence, or about thinking in particular, let’s focus on a single issue: given a program, can we decide whether it works or not? This is very ambitious because we should be able to specify what programs should produce for every possible input, so let’s tone down the question a bit. Instead of that very general first question, let’s just think about applying AI to detect whether a function may end in an infinite loop. If a function loops forever, we’re certain the function is not correct, so at least that’s a good step forward. We may not know if a function works well, but we may be sure if it doesn’t.

An aside: if we could decide whether a function will always stop, we’d be able to prove mathematical theorems very simply! For instance, suppose we wanted to see whether the Goldbach Conjecture (which says that every even number greater than 2 can be expressed as the sum of two prime numbers) is true. We could write a goldbachTest() function that would test if the conjecture was true for ever-increasing values 4, 6, 8, 10... etc., stopping only if the conjecture failed for some value. If we applied our "loop detection" function to goldbachTest, and it said that the function would loop forever, we'd know the conjecture was true, and false otherwise!

Let’s start thinking about our problem, detecting whether functions are “infinite-loop-less” or not. Is this possible? For at least some functions, the answer is “yes”. For example, if you consider functions that do not include looping statements (while, for) and do not call other functions (or themselves, using recursion), we can be sure they must always end. Furthermore, recognizing these very special "linear" functions could be done by a program that wouldn't even need AI; you can write it with ease.

However, we want to be able to work with any function and see whether it may enter an infinite loop. What about using AI and ML to detect them? For example, how do we teach a machine to recognize cats? An ML method is based on processing lots of pictures, some of which show cats and some do not. Eventually, a decision engine “learns” to distinguish cats from non-cats, and this has been done many times.

In that way, we could think of teaching a machine to recognize looping functions by feeding it with lots of different functions, some of which are loopless and some of which are not, and hope that the ML method produces our desired result: an algorithm capable of deciding whether any function may or may not enter an infinite loop. But would this work?

A paradoxical limit

The ML idea is there, and we know it can work, at least for some problems; could it work for ours? Let’s suppose it would: our process would end by producing our desired willLoop(fn) function that, given any fn function, would precisely return either true (if the function could enter an infinite loop) or false (if the function would always be guaranteed to finish).

But the (assumed) existence of this willLoop function implies an inevitable paradox! To see it, imagine we wrote a mystery(fn) function as shown below:

function mystery(fn) {
  if (willLoop(fn)) {
    return true;
  } else {
    while (true) { 
      /* loop forever! */
    }
  }
}

What does mystery do? Given a fn function, if:

• fn will loop in some case, mystery returns true
• fn will never loop, mystery enters an infinite loop

And now, the big question: what happens if we call mystery, giving the mystery function itself as its parameter?

Don’t object to the idea of feeding a function with its own code. For instance, Prettier is written in JavaScript, and we can use Prettier to format itself. Similarly, we can use ESLint to detect problems in its own code. Even if it may be a bit unusual, in principle, there’s no objection to calling a function with its own code as an argument.

Let’s analyze what happens if we call mystery(mystery).

• if willLoop(mystery) returns true (meaning that mystery will loop forever), then mystery will return a value and finish
• if willLoop(mystery) returns false (meaning that mystery will never loop), then mystery will enter an infinite loop.

This is contradictory! There’s no way out of this paradox (similar to Bertrand Russell’s “Barber Paradox”) other than deciding that mystery cannot exist, and this implies that willLoop cannot exist either... pity!

In computability theory, we would say that our problem, detecting whether functions may or may not enter an infinite loop, is undecidable. The “Halting Problem” was shown in 1936 to be another undecidable problem; Alan Turing later provided a different proof of the fact.

Conclusion

The limits and capabilities of AI, based on ML or not, are clearly growing every day, and we don’t yet know how far they may go. However, as we have shown here, applying AI and ML to the problem of deciding if a function may enter an infinite loop is unrealistic and cannot succeed without producing an impossible logical paradox.

There are limits to AI, after all!

See how users are using your site as if you were sitting next to them, learn and iterate faster with OpenReplay. — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data. Check our GitHub repo and join the thousands of developers in our community.

Originally published at https://blog.openreplay.com.