Intuition, puzzles and computability

    In this article I want to talk about one paradox that has been noticed a long time ago, but which is still a mysterious mystery - one of those that teachers talk about 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 later, and for starters, I will tell you how I devised my own program in solving simple, seemingly, puzzles from the game Still Life.



    The puzzle consists of five reels with card suits, so each reel can take four positions.



    When you click on one of the reels, he turns himself and some others, that is, each drum has its own pattern. Moreover, the rotated drum itself always rotates clockwise, while the rest can rotate as desired or not rotate 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 rotation clockwise, -1 is counterclockwise rotation, 0 is no rotation.

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

    Task: find the sequence of rotations of the drums, bringing the system to the state 0 0 2 0 0.

    It was in the evening. I was too lazy to pick a puzzle, and I decided to write a program that would solve it for me. But I was too lazy to write any complicated program, so I decided to use brute force. Obviously, the solution to the problem can be represented as a quaternary number of some unknown length. Each digit of this number will represent the selection of one of the reels in the step corresponding to the digit category. Then brute force comes down to enumerating all pentadic numbers until a solution is found. For each length of the number, the number of iterations will be 5 n , where n is the length of the number. In the worst case, the algorithm will work out 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 small and launched brute force. I went to the kitchen, prepared tea, drank it (a mug of tea with me is a measure of time equal to about 20 minutes), - the brute force hung somewhere at n = 10. Realizing that this was a long time, I decided nevertheless dig a puzzle yourself. To my surprise, I picked up a combination of about ten minutes, - brute force still hung somewhere at n = 10.

    At first, I thought that a solution could be found faster using A *, but it turned out that because of the reticence of the search space, finding a valid a priori estimate is not so easy. Say, if we take the number of mismatches of the current and final patterns as an a priori estimate, such an estimate will give 3 always when there is only one step left to solve. I am sure that it is possible to come up with a valid a priori estimate, but the proof that it is admissible is most likely non-trivial. I never came up with an apriori assessment (let it be a task for the habrasociety), but, in truth, I didn’t do it very much, because, with the help of my colleagues, I found another, simpler solution.

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

    Yes, the task was ultimately solved algorithmically, by computer, faster than any person is capable of, but here is the paradox: I solved the problem, but at the same time I could not formulate the algorithm by which I solved it. It’s not that I forgot it - I know for sure that I didn’t invent or use any clear strategy either before or during the solution, that is, I solved the problem irrationally - by typing.

    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 by which any ordinary person solves any puzzle, and since this puzzle was part of a computer game, it is unlikely that it requires knowledge of discrete mathematics from the player. It is designed for a solution in this way, and even more so it is not assumed that the player will sort 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 classic problem - the problem of algorithmic solvability. Since any computing process can be implemented by a 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 solutions has been 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 a concatenation of some arbitrary Turing machine and some arbitrary data for input to it (it is assumed that there is a consistently recognizable separator between the machine and the data). We need to build a Turing machine that returns 1 if this machine stops at this input and 0, if she goes into endless computing. It is proved that such a Turing machine is impossible to create. However, in practice, if you give a non-trivial, but not very long Turing machine and a sequence of bits of mathematics, then in most cases it will determine whether the calculation stops or not. The same goes for other algorithmically insoluble problems. Their special cases are solvable with a pencil and paper, but in each case the solution is different, and they are all irreducible to one universal method. The whole point is the need for a primary hypothesis. The same goes for other algorithmically insoluble problems. Their special cases are solvable with a pencil and paper, but in each case the solution is different, and they are all irreducible to one universal method. The whole point is the need for a primary hypothesis. The same goes for other algorithmically insoluble problems. Their special cases are solvable with a pencil and paper, but in each case the solution is different, and they are all irreducible to one universal method. The whole point is the need for a primary hypothesis.

    Any science, no matter how accurate, is advanced by hypotheses. To explain the law of nature or to prove a theorem, the scientist first 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 in solving a puzzle. The scientists of exact sciences are equally well versed in formal methods of proof, but outstanding scientists differ from the usual ones in that the hypotheses generated by their intuition turn out to be more accurate. At the moment, neither psychologists, nor neurophysiologists, nor even mathematicians can give an answer to the question: how does the hypothesis arise,

    Also popular now: