[FOM] Turing machines, algorithms, and category theory
paul at personalit.net
Wed May 3 16:10:22 EDT 2017
On 5/1/17 00:08, Patrik Eklund wrote:
> Recursion resides in set theory, and cannot easily be abstracted away
> from it.
Recursively definable sets reside in set theory for sure.
But recursively generated syntax is a linguistic fact, independently of
set theory. It is representable in the lambda calculus, for example,
and in theories of arithmetic and logic.
I would say that recursion is used by a theory, not that it resides in a
More information about the FOM