Questions related to computability theory, a.k.a. recursion theory

The theory of computability studies which functions can be computed using which machine models.

Computability theory (also known as recursion theory) is a branch of mathematical logic and computer science. It is mainly concerned with computability.

When some resource is restricted (such as time or space), then the tag is more appropriate.

history | excerpt history