What is a Turing stop problem?

Question

I’ve read and reread on Wikipedia, I’ve watched some 15 videos in English and Portuguese on this subject, I’ve read several articles on google, but I can’t understand.

Why would she go into an infinite loop? Or why would she stop? All the explanations using contradiction don’t make sense in my head.

Please, no technical terms. Help me with simple logic to understand.

Answer 1

What is a Turing machine for laypeople?

A Turing machine is a minimalist mathematical model of a computer with an infinite memory. Although minimalist, all Turing machines are capable of simulating each other. That is, all computers with infinite memory are able to simulate each other (even if the performance is bad).

So once you have an unlimited amount of memory, you can solve any computational problem, right? No!

The problem of the parade

The halting problem is the first problem that has been proven to be computationally unsolvable regardless of the amount of memory available. To see why, let’s elaborate the problem of the parade in this way:

I need a computer program (termina) that is able to inspect the code of another computer program (P) to determine whether or not he enters an infinite loop when given the input C. The program termina should lead to "Yes" or "Not" in a finite time.

Let’s assume you’re going to design the program termina with the programming language you want using the techniques you want. A way to check if P can enter an infinite loop with the input C is to simulate it with such input and keep monitoring each individual state of the memory of P. If the program P repeat some state of memory, then he safely entered an infinite loop and program termina responds "Not". If the program P finish its execution (stop), then surely it did not enter an infinite loop and the program termina responds "Yes". However, that’s not all.

The program P can occupy more and more memory as it processes input C, and even if/when consuming the entire input, still not stop and continue consuming more and more memory (which remember is infinite, and therefore it can consume as much as you want). This way, it is possible that it never stops and also never repeats a state of memory. With this, the program termina will need to be smarter than simply monitoring memory states for a repeat or a completion of P.

If the program P consumes more and more memory infinitely, the program termina could see if this memory follows some pattern of repetition. However, this also does not work, as will the program P is producing the digits of π infinitely and therefore there would never be repetition in that pattern. The program termina could determine that after consuming a very large number (X) of memory cells, then P not stop, but will that after X + 1 memory cells it would stop?

Example 1 of why the halting problem is difficult

The program termina can inspect the program structure P to determine if it would stop, but let’s assume that the program P be the program collatz below*, written in Python:

def collatz(n):
    while n != 1:
        print(n)
        if n % 2 == 0:
            n = n / 2
        else:
            n = n * 3 + 1

This is a very simple program. The value n is the input. When the n reaches 1, the program ends. If the n is even, it is divided by two. If it is odd it is multiplied by 3 and is added to 1. It will print a sequence of numbers until n reach 1. See here this program running on ideone for number 127. The image below shows a graph with the numbers generated in this process:

*^{:I took this program and also this image wikipedia}

If I set a pretty big number for the n, Will it stop at eventually producing 1? Or will it generate ever larger numbers indefinitely forever? The answer is that it is not known. This is a mathematical problem (collatz conjecture) proposed in 1937 for which no solution is known, although it is believed that the answer is that it always stops. If your program termina determine whether this programme collatz to, then termina is a program capable of solving this conjecture in finite time. It means that termina would have to be programmed with sophisticated enough techniques to prove unsolved mathematical conjectures.

Example 2 of why the halting problem is difficult

Another example (also in Python):

def reversed_string(a_string):
    return a_string[::-1]

def lychrel(n):
    s = str(n)
    if s == reversed_string(s):
        print(s + ' é palíndromo!')
        return n
    m = int(reversed_string(s))
    c = m + n
    print(s + ' + ' + str(m) + ' = ' + str(c))
    return lychrel(c)

In this example, the input is a number n. If n is a palindromic number (also called a Capicua, that is, equal to itself from back-to-front), it is returned. If it is not, of that number n, a number is produced m that is n back-to-front and then the two are summed up producing c which is used recursively as a new n until a palindrome is produced. To make it clear what the program is doing, it prints out all these numbers that it generates. See here the program working on ideone for the number 468.

The function lychrel ends when the input is the number 196? This is another open mathematical problem. A Lychrel conjecture says it would always end, but it is believed that this conjecture is false and that 196 would be her first counterexample. Again, since this is an open mathematical problem, no one knows the answer, and after a few billion iterations that produce numbers with billions of digits, a palindrome insists on not forming, but it is not known whether one would eventually form with a trillion, a quadrillion or a zillion iterations or if in fact it would never form. See here the program running on ideone for number 196.

If your program termina to examine the programme lychrel to determine (in finite time) whether it ends with entry 196, it would need to be able to either determine when it would end or then figure out a reason why it would never end, and thereby solve another open mathematical problem. Again, to do this, this program termina would not be something simple.

Example by diagonalization of why the halting problem is difficult

And then we fall into the test by contradiction from the diagonalization. Imagine that the program P were that:

import termina

def malandro(entrada):
    if termina(malandro, 'não importa'):
        while True:
            print('Estou num laço infinito')
    else:
        print('Acabou')

That program is malandro. It consists of the following: Knowing that the program termina determines if another program stops with any input, the program malandro uses the program termina to determine whether it itself terminates with the input 'não importa'. If termina determine that malandro to, then malandro enters an infinite loop. If termina determine that malandro enters an infinite loop, then malandro ends.

That is, the program malandro, question to the program termina what he does and then does just the opposite! It means there is no such thing as the program termina give the correct answer when receiving as input the program malandro. That is, or the program termina is incorrect or it may not end in a finite time.

In this way, it is shown that there is no way to build the program termina that performs both correctly and in a finite time. Any attempt to construct it will, at least in some pathological cases, either produce the wrong answer or produce no response in finite time. Therefore, a flawless and perfect version of the program termina simply doesn’t exist.

And if the program could answer that it fell into contradiction?

A possible (and naive) solution would be whether the program termina noted that the malandro uses the program itself termina or else that it depends on contradictory conditions and with that, rather than responding "Yes" or "Not", answer "impossible to determine".

That wouldn’t work either. Let’s assume that the program malandro2 has within you a copy of the program termina, but with all variables and functions renamed and encrypted. The program termina would have to determine that there is a copy of itself within the program he wants to analyze. And then the program would be this:

import copia_malandra_de_termina

def malandro2(entrada):
    z = copia_malandra_de_termina(malandro2, 'não importa')
    if z == 'Sim':
        while True:
            print('Estou num laço infinito')
    elif z == 'Não':
        print('Acabou')
    elif z == 'impossível determinar':
        print('Impossível determinar uma ova, acabou sim!')
    else:
        print('Haha, vai acabar do mesmo jeito')

I mean, no matter how sophisticated the program termina assumed to try to avoid the contradiction, there will always be an even more sophisticated way to defeat it. This reaffirms the hypothesis that the program termina simply doesn’t exist.

Other insoluble problems

One way to prove that a problem is insoluble is to reduce it to the halting problem. The way to do this is by contradiction. Let’s say that sbrubbles is the name of our unsolvable problem and that we have some hypothetical library with a program sbrubbles_solver somehow solve it. If you can devise an algorithm that when using the program sbrubbles_solver be able to provide a solution to the halting problem so you get into it:

• If there is a program to solve the problem sbrubbles, then we can use it to create a solution to the halting problem.
• We know that we cannot create a solution to the problem of stopping.
• Hence, by modus Tollens, we cannot create a solution to the problem sbrubbles.

Therefore, through this technique of reducing a problem Q to the problem of stopping, it is possible to prove that Q is an insoluble problem.

It is true that to elaborate an algorithm that in theory would solve the halting problem by taking advantage of a hypothetical function/program that solves the problem Q may not be simple task. However, this is exactly how many problems are shown to be insoluble.

In particular, according to the rice theorem, Determining whether any computer program has any nontrivial semantic property is an insoluble problem. Trivial property means those that are valid for all programs or for no program (and therefore, non-trivials are those that are true for some and false for others). By semantic property, it is understood by properties about the behavior of the program. The reason for this being insoluble is that the programme in question can, in the same way as the programme malandro, use the program that determines whether it itself contains such a semantic property to produce a contradiction. Therefore, it is an insoluble problem to design any algorithm To who tries to decide something about the behavior of another algorithm B without any error, limitation or infinite loop in the algorithm To.

Answer 2

The halting problem is usually provided as follows:

Given a program and an input it accepts, will this program give me an answer? IE, it will at some point stop its execution?

Note: I have all the time in the world, but not infinite time.

Apparently, the answer should be yes. But... this is not always the case. Sometimes the program enters into an infinite loop. This can happen because the programmer who wrote it made a mistake, or because the programmer chose the wrong approach when dealing with the problem, or simply because the problem in question cannot be solved.

But are there problems that cannot be solved? Yes, there are. They are problems that, given an input, there is the possibility of the program entering into an infinite loop. Regardless of how good the program is. And it does not enter into infinite loop in a simple and trivial way. Some problems, such as recognizing whether a word belongs to an unrestricted grammar, or whether given a finite set of matrices n x n it is possible to obtain the null matrix by just multiplying (with repetitions) the elements of this set, the programs that solve such problems can enter recursions and never go back to some previous state.

Now, to answer the questions in the text... in the order I think most appropriate. And I’m trying to put the concepts as lightly as possible, but for the sake of correctness it will come at times when I will need to be too technical. Whenever possible I will try to separate a concept in the "lay" part, and leave a more technical and mathematical explanation below or linked.

... why it [Turing machine] would stop?

A Turing machine is a automaton. So the only thing she does is:

• read data
• write data

And it does this from an initial datum, called input. In decision problems you need a "yes" or "no" answer. And this answer is only useful at the end of the processing, when the Turing machine is stopped. Acceptance or rejection of the entry can be done by writing, but it is usually more useful to know if you are in an accepting state or not.

Why would she [Turing machine] go into infinite loop?

Because there are insoluble/undecidable problems. @Guilherme Bernal proposes a heuristic to look for cases to identify when a software enters an infinite loop in that matter, but I pointed out a case "trivial" failure of the programmer that he could not detect with his heuristic. I also pointed out another "uglier" heuristic that is lighter, but with a smaller amount of false positive for "program in infinite loop".

(Spoiler Alert: technical part started) An example of a problem that is undecidable is whether a word can be obtained from an unrestricted grammar.

An unrestricted grammar is a grammar that accepts productions of any kind. See more here, here.

In other words, this problem is w ∈ L(G):

• w is the word we want to know if it can be obtained from grammar
• G is the unrestricted grammar in question
• L is the "language function", which given a language, returns all words that can be generated from it

In infinite language grammars, compute L(G) in its completeness is... infinite too. Perhaps infinite times some nonzero polynomial?

So there must be some way to check without having to list all the words, right? Well, that depends on the grammar.

In the case of regular grammars, it is trivial. The first step, however, is to transform the problem into a deterministic finite state automaton (see more here). After that, it is just feeding the automaton with the word and, if it stops in an accepting state, the word belongs to the language. Otherwise, it does not belong to the language.

For context-free grammars, you could normalize to Chomsky’s normal form and try to assemble the derivation tree by ascending strategy. If you get the non-terminal S at the top, then belongs to grammar, otherwise (found another non-terminal or found no answer at all) then does not belong.

For context-sensitive grammar, it starts to get complicated. There is no direct way to go. The most we can do is turn it into a non-recurring grammar. Every context-sensitive grammar can be transformed into a non-recurrent grammar so thatL(Gsc) = L(Gnr), where Gsc is the context-sensitive grammar and Gnr is the non-recurrent grammar. An interesting property of non-retail grammar is that a sentential form can only be derived in sentential forms of the same size or larger. So if the intermediate sentential form is greater than the length of w, we already know we’re on the wrong track, so just go back and try another way. And, yes, the most efficient context-sensitive grammar solution is to list in depth all possible transformations and cut when the intermediate form is too large.

For unrestricted grammars... well, they can be written so as to be retractive... even there is nothing prohibiting the consumption of a terminal generated in the middle of a production. So limiting by the size of the sentential form is not a good one for the general case.

What to do in this case? Well, the best that can be done is to construct the derivation graph. This same graph can be used for other restricted grammars as well.

How does this graph work? Well, we start with the initial nonterminal vertex, S. So we check what are the productions that this vertex can undergo, and for each production we take the vertex P1, P2... Pn for each of the n possible productions and links with edges to the originator vertex. If one of the productions generates a sentential form Pi already known, we should connect to this vertex instead of creating a new vertex. Then we add all the vertices in the structure of future visits and mark S as already visited.

The next step is to take the next vertex of the structure of future visits and, on top of it, make all possible derivations, add the new vertices and new edges in the graph, adding the neighboring vertices in the future visiting structure to, then mark the vertex as visited. Of course, if a vertex has already been visited, one should not do this processing again.

If the vertex being visited is composed only of terminals, then we can check whether Pv = w. If so, we find the answer, otherwise we know nothing.

In the case of non-retail grammars, the proper structure for storing future visiting vertices is stack, making a deep-sea search. This is because it is known that since grammar is non-recurrent, there is a maximum limit of vertices that can be generated in the middle of the path. If there are n non-terminal, I just need to examine at most (n+len(w))^len(w) distinct vertices as there are n+len(w) distinct symbols in grammar that are relevant to the word w and any sentence form Pg such that len(Pg) > len(w) implies that w cannot be obtained from Pg.

In the case of unrestricted grammar, the best structure to do this analysis is the queue. This will allow you to do a search in width of the derivation graph. Using the search in width avoids falling into a hole of perdition that even exploring the infinite possibilities of it does not arrive in w, because the processing of other paths continues to be done.

If it is possible to answer "yes", occasionally in one of the vertices it will contain w and guaranteed to pass through it from here until the end of time. If it is not possible, there are two hypotheses:

1. All paths have been investigated to the end, so grammar generates a finite language
2. At least one of the paths is an endless well and the program will continue to explore this well in width, adding new vertices to be visited

In the second case, the Turing machine will not stop.

All the demonstrations using contradiction don’t make sense in my head.

Well, I guess that means you have doubts about how to prove that the halting problem is undecidable. Let’s use the previous problem to clarify this?

If you, dear reader, have skipped the previous section after seeing the Alert spoiler: technical part started, I will briefly recap what the problem is. I wonder if a word w can be generated from an unrestricted grammar G. We then model a graph that represents all the sentential forms that I can obtain from a prior sentential form obeying the rules of production of G and do a wide search.

The possible results are:

1. if w can really be generated by G, after "some" processing we will find w
2. if we try to go across all the paths and they ended up not finding w, then the language L(G) generated by G was finite and we enumerated all its elements and none of them were w
3. one of the paths is an endless well, in which the search in width will continue indefinitely generating new vertices aimlessly, without ever leading to w

We know these results because somehow we know a priori whether w ∈ L(G). And what would happen if we really didn’t know the result of the algorithm?

In this case, we will need to wait for the algorithm to give an answer (1), enumerate all possibilities and none of them are w (2) or that it enters an infinite loop (3).

The cases (1) and (2) are trivial. After all, if it stopped, it stopped, we have the answer. And for the case (3)? @Guilherme Bernal provided a heuristic in that matter. But unfortunately it doesn’t work for the general case.

Looking at it from a different perspective... I’m going to let my Turing machine work for a while. I let it process for... two weeks. After that time I pause it and check its internal state. Well, it says that there are still paths to be cleared, vertices not visited. So I let her process a little bit more. I go back five years later, and then what? Well, now there are two billion vertices to be visited. I’m scared, but that means she’s making progress... or not?

Well, maybe next second she’ll just stop and yell, "I’m done, I thought w". Maybe it takes another week. Or two centuries. Impossible to determine that by looking at it. Maybe these two billion vertices are two billion endless wells. Or not! Maybe they can all generate w in the future, near or distant. Maybe processing is leading somewhere, maybe it’s just processing in vain.

By taking a Turing machine that solves the problem of whether w is generated by G and it is still in processing, it is impossible to determine whether it is because it is on its way to (1) or (2), or whether it is in perdition in (3).

This is an example that shows the impossibility of determining whether a given Turing machine will one day give an answer. After all, I have all the time in the world, but not infinite time.