Algorithms vs. Machines

Yuri Gurevich

Bulletin of the European Association for Theoretical Computer Science Number 77 |

In a recent paper, the logician Yiannis Moschovakis argues that no state machine describes mergesort on its natural level of abstraction. We do just that. Our state machine is a recursive ASM.