Recursion in programs, thought, and language

• by Sunny Khemlani
• in News
• posted December 21, 2021

Phil Johnson-Laird, along with his collaborators Monica Bucciarelli, Robert Mackiewicz, and myself, published a paper in Psychonomic Bulletin & Review that reviewed research into how humans consciously reason about recursive operations. Though the term “recursion” is often used by computer scientists to describe specific types of programs, people without any background or training in computer science can engage in recursive reasoning. Even children do so: such as when they perform and describe repeated loops of operations to solve a problem. The paper describes a simulation-based theory of how people reason about recursion: they construct kinematic simulations to carry out loops of operations, and use those simulations as the basis of their descriptions. It also discusses the computational power needed to carry out recursive reasoning and linguistic operations.

The abstract of the paper is here:

This article presents a theory of recursion in thinking and language. In the logic of computability, a function maps one or more sets to another, and it can have a recursive definition that is semi-circular, i.e., referring in part to the function itself. Any function that is computable – and many are not – can be computed in an infinite number of distinct programs. Some of these programs are semi-circular too, but they needn’t be, because repeated loops of instructions can compute any recursive function. Our theory aims to explain how naive individuals devise informal programs in natural language, and is itself implemented in a computer program that creates programs. Participants in our experiments spontaneously simulate loops of instructions in kinematic mental models. They rely on such loops to compute recursive functions for rearranging the order of cars in trains on a track with a siding. Kolmogorov complexity predicts the relative difficulty of abducing such programs – for easy rearrangements, such as reversing the order of the cars, to difficult ones, such as splitting a train in two and interleaving the two resulting halves (equivalent to a faro shuffle). This rearrangement uses both the siding and part of the track as working memories, shuffling cars between them, and so it relies on the power of a linear-bounded computer. Linguistic evidence implies that this power is more than necessary to compose the meanings of sentences in natural language from those of their grammatical constituents.

And the paper is available for download here.