I know that an algorithm can't decide whether another algorithm halts on an input or not (a Turing machine can't decide whether another Turing machine will halt on an input). But I, as an human, can: I mean you just don't end up in your activity as a programmer with a looping algorithm and you don't know why!

To do this, you generally analyze the (somewhat) natual language of the code you wrote. Considering this, it comes to no surprise to me that for a machine this is hard to do: if I had to write a convicing chatbot (also a problem in the realm of natural language) in a programming language with traditional techniques it would turn out to be pretty bad. But why is that? Is there any term or concept that clearly differentiates between what humans are able to do, what machines are able to do and why is there exists this distinction?

Also, it seems to me that with advacements in artificial intelligence developement it won't be long until a machine will be able to carry out the aforementioned tasks (in particular loop detection). How does that relate to our traditional computability model? I mean artificial intelligence is still powered by algorithms, does't that violate it?

  • 1
    $\begingroup$ You, as a human, cannot decide for every algorithm and input whether it halts. $\endgroup$
    – gnasher729
    Commented Dec 5, 2023 at 17:55
  • $\begingroup$ @gnasher729 Could you provide an example? $\endgroup$
    – lilsm
    Commented Dec 5, 2023 at 20:27
  • 1
    $\begingroup$ FLT if your name is not Wiles. A program checking whether an even number is the sum of two primes. A program that checks if the Collatz sequence ends. It’s the Church-Turing thesis. $\endgroup$
    – gnasher729
    Commented Dec 5, 2023 at 20:55

1 Answer 1


Your question contains so many sub-questions and claims, making it really hard to answer, but I will try my best, starting with debunking your claims.

No, You Cannot Predict Halting!

You are conflating loop detection with the halting problem. Loops are only the very simplest type of recursion. Modern code analysis can already detect most kinds of infinite loops. But those are trivial in the grander scheme of the halting problem. I really encourage you to read Alan Turing's original proof of the halting problem. It is simple and really clever. It does not matter what kind of smart Turing machine "oracle" program You write. Alan Turing would wrap it in another program whose halting cannot be predicted by that "oracle", i.e. it's not an oracle!. "AI" running on Turing machines is not able to escape the halting problem.

You, as a human being, cannot predict halting of a Turing program either! Consider the following program:

while(true) {
  compute more digits of pi;

  if( computed digits of pi contain the ASCII-encoded text of the bible )

Does this problem halt? Mathematicians believe that it does, but they do not seem to know. If you can predict the halting of this problem, you have just given a new mathematical proof. And while You're at it , you could also easily prove Goldbach's conjecture.

In order to appreciate, just how long the runtime of a finite Turing program can be, you should look into the Busy Beaver Numbers. Astronomical does not even begin to describe these numbers...

Why Can't humans Translate All of their Abilities Into Algorithms?

Now let's get to the core question. When teaching a human ability to a machine, I see the following two key requirements/challenges:

  1. You must be sufficiently aware of how the ability works
  2. You must be able to describe that ability to a computer

On a basic level, computers work on binary numbers, arithmetic and logic. The field of mathematics is one that we humans very consciously developed. So it comes as no surprise that mathematical problems, like linear equation systems, were the first to be solved by a computer.

In the years since, we have become better and better at solving challenge #2. We have developed better and better programming languages, input devices, editors and design tools to better teach/tell a computer what to do.

Challenge #1, however, is almost unsolvable. There are so many things that we humans do without thinking about them. They are encoded into our genes, and/or learned subconsciously. It is incredibly hard to describe how we do these things. How do we detect objects in 3-dimensional space? How do we compare images? How do we identify noises and percieve languages? How do we walk? How do we grab things and pass them to other people? How do we feel empathy, sympathy, apathy and antipathy for other people? How do we feel, emit and perceive emotions?

Will "AI" Help?

Yes and no! "AI" will certainly help us with challenge #2 by enabling all kinds of new human-machine interfaces. Telling our computer what we want to achieve will become much simpler than typing in rigid code.

It is not so clear, however, if "AI" will help us solving challenge #1. Sure, we can teach a machine how to detect an object in an image already, or how to summarize text and answer questions. But that does not mean, we have taught human abilities to the machine. We have taught it to imitate human abilities. It's an important distinction, I would argue. It's like a Psychopath, practicing how to cry in front of a mirror and learning simple rules about when to cry. It may look like grief, but it isn't.

There's one way I can see how current "AI" could help us with translating more human abilities into machine code: "AI" could help us improve our understanding of neurobiology.

You may argue that imitating human abilities is good enough. In that case, we are making a lot of progress already and will continue to do so in the near future, thanks to machine learning. There are, however, a lot of challenges. The training data, for example, may not be entirely representative of human behavior. Text data is notoriously bad at conveying tone and emotions, especially the short form, attention driven text posted on internet platforms. The physical distance and anonymity provided by the internet also promotes apathy. Narcissists may produce a lot more text on the internet than mentally sane people. On top of that generative "AI" will soon flood the internet with spam indistinguishable from human spam. If this text data is used for training machine learning models, it will create a distorted imitation of human behavior.

  • 1
    $\begingroup$ Thank you for the answer, I understood now! I guess that this whole apparatus will hold true only if the Church-Turing thesis holds true, which is basically intuition on which to build the whole mathematical foundations of computing theory. So anything could still change and be challenged in the future. $\endgroup$
    – lilsm
    Commented Dec 10, 2023 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.