See Theory of computation. Here we are focusing on Turing computability. This is because, according to the Church-Turing thesis, Turing machines are the most computationally powerful, and all other realizable models of computation, are either special cases (i.e. they will define subsets of Turing computable functions) or equivalent.

https://mobile.twitter.com/_julesh_/status/1095540512168194048

Important concepts

• Formal language
• Turing machine

From Naïve Set Theory - Cardinality & Basic Computability Theory

Decidability of languages/sets

An input string $w$ is said to be accepted by a Turing machine $M$ if, the computation of $M$ with initial configuration having $w$ on the first tape and both heads at the left end of $w$, terminates in $q_a$, the accepting state.

The machine is said to reject the string if the Turing machine terminates in $q_r$, the rejecting state.

(There is of course, the possibility that the Turing Machine may not terminate its execution.)

a Turing machine is said to accept a language L if every string x in the language is accepted by the Turing Machine in the above sense, and no other string is accepted

Definition 1.2.2. A language is said to be acceptable if there is a Turing machine which accepts it.

A language L is said to be decidable if both $L$ and $L^c$ (complement) are acceptable.

Alternative Definition of decidability of a set based on computability of functions (see below).

Semidecidable set definition. It is an acceptable set, that is not decidable. Example of semidecidable set.

Computability of functions

Definition of computability

$f(x) \uparrow$ means undefined..

Useful definitions: bit-doubling function, pairing function. The pairing function is a prefix code - that is, the encoding of a pair cannot be the prefix of the encoding of another pair. See Prefix code. This makes the code uniquely decodable: a pair can be identified without requiring a special marker between pairs. (Pairing function)

Math 574, Lesson 2-4: Computable Functions

Definition of Turing computability

Partial computability Definition of partial computability <–> Semidecidable set definition

A weaker notion is that of semicomputability: Semicomputable function

Enumerability of functions from above and below, related to enumerable approximations to the function

Computable enumerability

Theorem 1.2.10: A language is computably enumerable (or recursively enumerable) if and only if it is acceptable.

Theorem 1.2.11: A language is decidable if and only if it is computably enumerable in increasing order. That is, a language $L$ is decidable if and only if it is finite or there is a total computable bijection $f: \mathbb{N} \rightarrow L$ such that for all numbers $n$,

$f(n) < f(n+1)$

Theorem 1.2.12. Every infinite computably enumerable set contains an infinite decidable set.

See Computational Complexity problem sheet solutions offline version. Also see these notes on Kolmogorov complexity, for proof of Theorem 1.2.12. and more.

Universality theorem: There is a Universal Turing machine. Theorem (vid) (see also Godel numbers for indexing Turing machines)

Kleene's normal form theorem. There is a 3-ary partial computable function $C$ and a 1-ary partial computable function $U$ such that any 1-ary partial recursive function can be expressed as

$f_e(n) = U(\mu z[C(e.n.z) = 0])$

Theorem 1.2.15 There is a partial computable function that is not total computable.

Uncomputable functions

Halting problem

Other examples

Solvability of diophantine equations.

Word problem for groups

Kolmogorov complexity

All computable functions on real numbers are continuous!