Recursion in programs, thought, and language

Area of Science:

• Cognitive Science
• Linguistics
• Computer Science

Background:

• Recursion is a fundamental concept in computability logic, where functions can be defined in terms of themselves.
• Understanding how humans, particularly naive individuals, generate and execute recursive processes in thinking and language remains a challenge.

Purpose of the Study:

• To present a novel theory explaining recursion in human thinking and language.
• To investigate the computational mechanisms underlying informal program generation in natural language.
• To explore the role of kinematic mental models and instruction loops in recursive task execution.

Main Methods:

• Developing a computational model that generates programs to explain recursion.
• Conducting experiments where participants simulate instruction loops using kinematic mental models.
• Analyzing task difficulty using Kolmogorov complexity for recursive rearrangements.

Main Results:

• Participants spontaneously used loops of instructions in mental models to compute recursive functions.
• The difficulty of recursive rearrangements correlated with Kolmogorov complexity predictions.
• The computational power required for these tasks aligns with linear-bounded automata.

Conclusions:

• Human recursion in thinking and language can be explained by computational loops, not solely by self-reference.
• Kinematic mental models and simulated instruction loops are key mechanisms for naive recursion.
• The computational demands of natural language composition may be less than previously thought, given the power of linear-bounded computation.