Mental simulation and the construction of informal algorithms

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.


Back to Table of Contents