Untitled attachment

Notices where this attachment appears

1. Embed this notice
   John Carlos Baez (johncarlosbaez@mathstodon.xyz)'s status on Thursday, 07-Nov-2024 00:49:46 JST John Carlos Baez

   in reply to

   @julesh - "Basic question but I'm not 100% sure: it's not possible to have a "reasonable" syntax that captures exactly the total computable functions N → N, right?"

   I'm pretty sure that's true, but we should phrase it in theorems so we can spot loopholes. Here's what I know. The set of total computable functions is not computably enumerable: there's no total computable function f: ℕ²→ℕ such that every total computable function ℕ→ℕ is one of the f(i, -): ℕ→ℕ. The proof is an easy diagonal argument.

   So then the question is whether "a reasonable syntax that captures exactly the total computable functions ℕ→ℕ" must give a way to computably enumerate these functions.