So long, and thanks for all the fish.

Douglas Adams fourth book was titled “So long, and thanks for all the fish“. Its title is the message left by the dolphins when they departed Planet Earth just before it was demolished to make way for a hyperspace bypass. Reading this begs one to wonder if humans are as intelligent as we make ourselves out to be. For a long time we presumed that we were the only intelligent beings in the universe. This is highly unlikely of course. Dolphins are of course highly intelligent, and self-aware. They use tools, communicate, and have emotions. Just because their intelligence doesn’t mimic ours, doesn’t mean they lack aspects. They are restricted by their environment of course, and their lack of hands. What we do not understand we sometimes put down to a lack of intelligence. Maybe some species are happy being where they are, and humans are never content doing anything but evolving, at least from a societal viewpoint. Why do we need faster cars? Why do we need to explore the cosmos? Why do we need artificial things? 

The answer likely lies in what the dolphins comprehend, and what we are too ignorant to ever fully accept – life is simple – go with it. 

Musings on why the Towers of Hanoi is hard to comprehend

So we have looked at the recursive solution to the Towers of Hanoi (ToH), and it seems somewhat magical. If you work through the trace line by line, you can see how the problem is in its essence recursive. Then why is the Towers of Hanoi a horrible recursive problem for novices? Towers of Hanoi may not be very appropriate for a novice programmer, because although the problem seems easy, and the solution exudes elegance, trying to explain the solution is far more convoluted.

whatpeoplethinkTOH

Part of the problem lies with the problem itself. It is best illustrated in a tactile manner, so that it can be physically manipulated. It works on paper too, but obviously playing a game is much easier.

Before it’s use as one of the poster-children for recursion, the “Tower of Hanoi” was actually used in experimental psychology. One study from 1962 looked at the effects of verbalization on problem solving [1], or more specifically investigating how acts of verbalizing during problem solving result affected problem solving effectiveness. Here however they refer to the problem as the “three circle problem”, i.e. “the task of transferring discs graduated in size from one circle to another in a triangular configuration of three circles“. This work was based on previous work from 1932 [2], yet is a doppelgänger of the Tower of Hanoi.

The work [2] looked at solving the issue with a variable number of discs, from 3-8, even asking participants to “try and find a general rule by which the problem may be solved“. The authors pose a series of differing trials, some with generalized instructions, others with none. When participants were finished solving 8 discs, they were asked for (i) a general statement of the most efficient way of transferring any number of discs, and (ii) a formula for computing the least number of moves necessary for transferring any number of discs. What was clear from the experiments is that the task, although a tactile one, was difficult for the subjects. Some took upwards of 3 hours, and one participant made nearly 15,000 moves. It was evident that those groups provided with generalized instructions fared better than those with none, who were not even able to formulate a generalization.

Indeed there has been some exploration into why problems like Tower of Hanoi are hard to solve from a problem solving perspective [3]. But why the difficulty? Here are some insights [3]:

  • The problem rules can be a major source of difficulty.
  • Rules consistent with real world knowledge aid problem solving, as does the physical representation in the ToH problem.
  • Intensive training on the rules significantly decreases the difficulty of the problems.
  • Participants cycle through a substantial amount of exploratory behaviour before they reach a point where they can proceed quickly to their goal.

Kotovsky et al. [3] concluded that problems that impose higher processing loads require more training. A problem solver has a limited amount of processing capacity that is easily overloaded by the memory requirements of unfamiliar problem rules. The difficulty in solving the ToH algorithmically is likely grounded in some of the psychological aspects of problem solving. In part it may be the digital nature of how the problem is presented. External representations such as a physical Tower of Hanoi game can serve as memory aids, extending working memory [4]. But external representations, can also be intrinsic to the problem, without them the problem may actually change in nature. They can be used to guide, constrain, and even determine cognitive behaviour [4].

The problem is that ToH, like similar problems can be solved using a physical game, or even on paper, however it is the process of making the solution recursive that is the issue. When solving the problem, people aren’t necessarily doing so using a recursive cognitive process. A computational function is recursive if (and only if), one of its processes is a call to itself. This results in an internal application of the same function, while at the same time keeping whatever it was doing before in memory, creating a chain of deferred functions. While it might be possible to solve the ToH with three discs using working memory, the more discs added to the problem, the harder this becomes.

[1] Gagne, R.M., Smith, Jr., E.C., “A study of the effects of verbalization on problem solving”, Journal of Experimental Psychology, 63(1), pp.12-18 (1962)
[2] Ewert, P.H., Lambert, J.F., “Part II: The effect of verbal instructions upon the formation of a concept”, Journal of General Psychology, 7, pp.400-412 (1932)
[3] Kotovsky, K., Hayes, J.R., Simon, H.A., “Why are some problems hard? Evidence of Tower of Hanoi”, Cognitive Psychology, 17, pp.248-294 (1985)
[4] Zhang, J., “The nature of external representations in problem solving”, Cognitive Science, 21(2), pp.179-217 (1997)

Recursion and the human mind

Although not completely natural, recursive thinking is uniquely a human trait, and it has been suggested that it is one of the characteristics that distinguishes human language from other forms of animal communication [1]. Corballis [2] suggests that recursion gives humans the ability to “mentally travel in time”. This is based on the idea of episodic memory, which refers to particular episodes of life that can be relived in our minds. This differs from semantic memory which is the storehouse of knowledge. Episodic memories are considered to be recursive, as they involve making mental references to an earlier mental self. Canadian neuroscientist Endel Tulving [3] suggests that recovery of semantic memories requires noetic awareness, which is simply knowing. Conversely, the recovery of episodic memories requires autonoetic awareness, or self-knowing. So episodic memories are recursive because they involves making references to an earlier mental self. Therefore the recursiveness of thought is intrinsically tied to the notion of self, or as Corballis puts it “not merely knowing that one is a physical object , but knowing that one knows, or knowing that one has mental states”. 

This concept is fundamental to the evolution of technology. Tool use is by no means unique to humans, however humans are the only animals that have been observed using a tool to make a tool, which is then used to make a tool [4]. A blacksmiths hammer is used to craft a hammer, which is then used to craft a hammer, etc. Development of tools requires travel into the past to explore previous designs of hammer, as  well as the future to envision new designs.

However the identification of recursive processes used on a daily basis is elusive, as they are often attributed to other methods [5]. Imagine if you will, a tree that has been felled. The act of de-limbing the tree (i.e. cutting off all its branches to leave just the trunk) could be thought of as a recursive process.

    de-limb(tree)
    begin
       if (tree has limbs)
          cut off lowest limb
          de-limb(tree)
       else
          done
    end

The problem is that this process is just as easily described in an iterative manner:

    de-limb(tree)
    begin
       while (tree has limbs)
          cut off lowest limb
    end

And in reality, this is how the process is perceived by humans. Humans don’t actively think about recursion. Sometimes we may actively use recursion to solve problems, but likely don’t realize it.

REFS
[1] Hauser, M.D., Chomsky, N., Fitch, W.T., “The faculty of language: What it is, who has it, and how did it evolve?” Science, 298, pp. 1569-1579 (2002)[2] Corballis, M., “The uniqueness of human recursive thinking: the ability to think about thinking may be the critical attribute that distinguishes us from all other species”, American Scientist, 95(3), pp.240-248 (2007)
[3] Tulving, E., Elements of Episodic Memory, London, Oxford University Press (1983)
[4] Beck, B.B., Animal Tool Behavior: The Use and Manufacture of Tools by Animals, Garland STPM Press, New York (1980)
[5] Vitale, B., “Elusive recursion: A trip in recursive land”, New Ideas in Psychology, 7(3), pp.253-276 (1989)