Intuition, puzzles and computability

In this article I want to talk about one paradox, which was noticed a long time ago, but which is still a mysterious mystery - one of those that teachers tell in order to interest students in their subject. This paradox is directly related to the problem of artificial intelligence, so this article was published in the corresponding blog.

But about this after, and for starters, I will tell you how I made my own program in solving simple, seemingly puzzles from the Still Life game.


')
The puzzle consists of five reels with card suits, so each drum can take on four positions.



When you click on one of the drums, he and some others turn, that is, each drum has its own pattern. And the rotating drum itself always rotates clockwise, the others can rotate as they please or not at all.

The patterns are as follows:

1 2 3 4 5 -------------- 1: +1 -1 +1 0 0 2: +1 +1 0 0 -1 3: 0 -1 +1 -1 0 4: -1 0 0 +1 +1 5: 0 0 -1 +1 +1 

Here +1 is a clockwise rotation, -1 is a counterclockwise rotation, 0 is no rotation.

If we denote the drum states by the numbers 0 1 2 3, then the initial state of the system will be: 0 2 0 3 1.

Task: to find the sequence of turns of the reels, leading the system to the state 0 0 2 0 0.

It was in the evening. I was too lazy to poke around with a puzzle, and I decided to write a program that would solve it for me. But I too was too lazy to write some complicated program, so I decided to use brute force. Obviously, the solution of the problem can be represented by a five-dimensional number of some unknown length. Each digit of this number will represent the choice of one of the reels in the step corresponding to the digit category. Then brute force is reduced to the enumeration of all five-part numbers until a solution is found. For each length of a number, the number of iterations will be 5 ⁿ , where n is the length of a number. In the worst case, the algorithm will work 5 ^{min (N)} , where min (N) is the minimum number of steps n for which the problem can be solved. I assumed that for this task this value is not large and I launched brute force. I went to the kitchen, made tea, drank it (I had a cup of tea - this is a measure of time equal to about 20 minutes) - brute force hung somewhere for n = 10. Realizing that it was for a long time, I decided pick it up yourself. To my surprise, I picked up a combination of ten minutes, - the brute force was still hanging somewhere on n = 10.

In the beginning, I thought that a solution could be found faster using A *, but it turned out that because of the intricacy of the search space, it was not so easy to find a valid a priori estimate. For example, if we take the number of discrepancies between the current and the final pattern as an a priori estimate, such an estimate will give 3 whenever there is only one step left to solve. I am sure that it is possible to come up with an admissible a priori estimate, but the proof that it is most admissible is not trivial. I didn’t come up with an apriori appraisal (let it be a challenge for the habrasoobshchestva), but, to tell the truth, I didn’t do this much, because, with the help of my colleagues, I found another, simpler solution.

Leaning into the office network, I ran a brute force on the workstation and went to bed. The next morning at the office, I discovered that my Core i5 did find a solution at a depth of 14 in some incredible number of iterations. There was no time to do this garbage at work, and I decided to connect the collective mind, sending the task to the team. The team answered with a question: is it possible to turn the drums back? According to the condition of the problem, it is impossible, as it were, but it is not difficult to prove that for each drum three turns forward are equivalent to one turn back. Thus, the solution can be represented by a decimal number, replacing a sequence of three identical digits with one. Changing the base of the degree, we reduce the exponent, and therefore reduce the number of iterations significantly. The modified algorithm found a solution for 300 with kopecks of iterations, on Core i5, for a fraction of a second.

Yes, the task was ultimately solved algorithmically, by a computer faster than any person is capable of, but here’s the paradox: I solved the problem, but at the same time I could not formulate the algorithm with which I solved it. Not that I forgot it - I know for sure that I did not invent or use any clear strategy, either before or during the decision, that is, I solved the problem irrationally - using a spear method.

The general solution scheme, however, can be formulated as an algorithm:

 TARGET_STATE = [0, 0, 2, 0, 0] #  . intuition = Intuition.new # . solution = [] # . current_state = [0, 2, 0, 3, 1] #  . while current_state != TARGET_STATE #    ,   . if !solution.empty? && intuition.bad_state?(current_state) current_state = do_step_back(current_state, solution.pop) else #        . step = intuition.get_step(current_state) solution.push(step) #  ,   . current_state = do_step(current_state, step) end end 

In general, this is a universal algorithm that any ordinary person solves any puzzle, and since this puzzle was part of a computer game, it is unlikely to require the player to have knowledge of discrete mathematics. It is designed for a solution in this way, and even more so it is not expected that the player will go through thousands of combinations.

This is my personal experience, but there is another, more vivid, example of this paradox.

In mathematics there is such a classical problem - the problem of algorithmic solvability. Since any computational process can be implemented by the Turing machine, the problem can be formulated as follows: for some problem, is it possible to create a Turing machine that solves it. There are many problems for which the impossibility of their algorithmic solution is proved, and one of these problems is the problem of stopping the Turing machine itself. Strictly speaking, a sequence of bits is given, which is the concatenation of some arbitrary Turing machine and some arbitrary data to feed it to the input (it is assumed that there is a consistently recognizable separator between the data and the machine). We need to build a Turing machine that returns 1 if the given machine stops at this input and 0 if it goes into infinite calculations. It is proved that it is impossible to create such a Turing machine. However, in practice, if you give a non-trivial, but not very long Turing machine and a sequence of bits to mathematics, then in most cases it will determine whether the calculation will stop or not. The same applies to other algorithmically unsolvable problems. Their particular cases are solvable with a pencil and paper, but in each case the solution is different, and all of them are not reducible to one universal method. It's all about the need for a primary hypothesis.

Any science, no matter how precise, is advanced by hypotheses. To explain the law of nature or to prove a theorem, a scientist first of all puts forward a hypothesis, for which he turns to intuition. Further, using mathematical formalism, the scientist proves or refutes it, and if the hypothesis is refuted, he puts forward a new one. In essence, scientists use the same method as any person when solving a puzzle. Scientists in the exact sciences are equally proficient in formal methods of proof, but distinguished scientists differ from ordinary ones in that the hypotheses generated by their intuition turn out to be more accurate. At the moment, neither psychologists, nor neurophysiologists, let alone mathematicians, can answer the question: how does a hypothesis arise, but only by answering this question can we talk about the possibility (or impossibility) of creating artificial intelligence.