New answers tagged

1

I am going to answer the question from your title in a slightly facetious way: Computable maps are closed under composition, and the identity map is computable, therefore the collection of all computable maps $\mathbb{N} \to \mathbb{N}$ forms a monoid with respect to composition. Perhaps you meant to aks whether there was a monad involved, in which case: ...


8

If recollection serves the answer is yes, although it is definitely not easy (so far as I know). The question was first posed by Shoenfield in the final paragraph of his paper Degrees of unsolvability associated with classes of formalized theories. I believe it was first answered by Peretyat'kin, who has proved a number of deep results about the model- and ...


Top 50 recent answers are included