Mental simulation and the construction of informal algorithms

Mental simulation and the construction of informal algorithms Sangeet Khemlani 1 and Phil Johnson-Laird 2 sunny.khemlani.ctr@nrl.navy.mil, phil@princeton.edu Naval Research Laboratory, Washington, DC 20375 USA Princeton University, Princeton NJ 08540 USA Abstract We describe two studies that show that when individuals who are not programmers create algorithms, they rely on mental simulations. Our studies concerned a railway domain in which carriages are rearranged – a simple environment but equivalent in computational power to a Turing machine. Participants successfully solved rearrangement problems (Experiment 1), and created algorithms to solve them (Experiment 2) and their performance corroborated the use of simulation. The participants tended to use loops and to prefer while-loops even though they are of greater computational power than for-loops. Their ability to create algorithms for abstract problems improved when they first had to create algorithms for more concrete problems. We devised a computer program that creates its own algorithms for rearrangement problems. It generates Lisp functions that operate on lists and creates descriptions of them in everyday language. The complexity of the resulting algorithms predicts participants’ difficulty in devising them. Keywords: algorithms, computer programming, creativity, deduction, problem-solving, reasoning Introduction A long controversy about human thinking is whether it depends on logic (Rips, 1994), probabilities (Oakford & Chater, 2007; Tenenbaum & Griffiths, 2001), or mental simulations (Craik, 1943; Johnson-Laird, 1983; Hegarty, 2004). Many inferences such as syllogistic deductions can be explained by mechanisms that depend on any of the three approaches (see Khemlani & Johnson-Laird, 2012, for a review). Indeed, few inferential tasks unequivocally depend on one approach. Computer programming may be such a task: it is readily explained by appealing to mental simulation (Bornat, Dehnadi, & Simon, 2008; Caspersen, Bennedsen, & Larsen, 2007; Kurland & Pea, 1985). To debug faulty code, programmers have to mentally simulate the algorithm to discover the situations in which the computer failed to produce the expected output. It is less apparent how mental rules of logic or probabilities could be used develop algorithms. Logic can be used to deduce the consequences of a program, but the creation of a program goes beyond logic (cf. Gulwani, 2010; Kitzelmann, Schmidt, Muhlpfordt, & Wysotzki, 2002). Probabilities hardly enter into the process, because computer programs are deterministic, and the language of the probability calculus is ill equipped to operate over the structures of programs. Mental simulation is therefore an appropriate framework with which to characterize the ability to create algorithms, and researchers can benefit from studying the simulations programmers use to solve tasks (Holt, Boehm- Davis, & Schultz, 1987). Expert programming depends on more than just mental simulation, however. Programmers often have specialized knowledge of programming languages, of relevant software platforms and tools, and about computer science in general (Boehm-Davis & Ross, 1992). For that reason, many studies have tested the ability of novice programmers to write computer programs (see, e.g., Anderson, Pirolli, & Farrell, 1988). Few have investigated how those without any background in programming try to create algorithms. Miller (1974) pioneered such studies. He examined the way college students unfamiliar with computers wrote instructions for others to follow, and found that they tended not to use loops in their instructions, even though they could understand them (Miller, 1981). More recently, Pane and his colleagues carried out a study in which they presented non- programmers with static descriptions of an agent moving in a popular video game, PacMan, and the participants had to summarize how agents moved in general. They again preferred not to make use of loops, but when they did, they appeared to rely on while-loops (Pane et al., 2001). Despite these results, there exists no psychological theory of how non-programmers construct algorithms. To develop such a theory, and to study algorithmic creativity in non- programmers, we designed a novel problem-solving task environment in which reasoners have to sort the order of a list in various ways. We introduce the environment below, and then explain how individuals build kinematic mental models to construct algorithms for their solutions. We then describe two experiments that show that reasoners intuitively understand the environment (Experiment 1) and that they can mentally create algorithms for the problems in the environment (Experiment 2). Rearrangement problems and the railway environment We studied how individuals who have never learned computer programming create algorithms in everyday language. For problems that they readily understood, we used the railway environment shown in Figure 1. The environment consists of a railway track and a siding. It is an analog of a finite-state device with two stacks – the left track (a) holds the input and also acts as a stack, the siding (b) acts as another stack, and the right track (c) holds the final output. Participants’ task is to move the cars from the left track to the right track into a specific order. Cars can move only from the siding to and from the left track, and from left track to right track. Multiple cars can be moved at once, i.e., any move of a selected car applies to all cars in front of it. For example, in Figure 1, if you moved the E car