N. Virgo
  • Member for 7 years, 11 months
  • Last seen this week
Minimal requirements for Kleene's recursion theorem
4 votes

I stumbled upon a (partial) answer myself, in David Madore's essay about quines. I quote, A different, perhaps more satisfactory, way of stating the fixed-point theorem would be to eliminate the ...

View answer
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
2 votes

Here is one that I think works, and is arguably not all that unnatural. We will start with a language along the lines of Hofstadter's BlooP. This is a simple imperative language in which the only ...

View answer