Computability and Logic

View source | View history | Atom feed for this file

This page contains scribbles and random musings as I process the contents of Computability and Logic. It’s not really for public consumption (unless you happen to care about my specific confusions).

Something that bugs me is that there is a classification of (partial) recursive(ly enumerable) sets, functions, etc. but textbooks seem to only state some of these results, rather than presenting a table with all the results visible at once.

Let be a partial or total function. If the {domain / range} of is {recursively enumerable / enumerable in increasing order} then is ____.

Let be a {recursive / recursively enumerable / recursively enumerable in increasing order} set. Then can be the {domain / range} of a {recursive / partial recursive / primitive recursive} function.

Also there are multiple ways to pass between functions and sets here.