Computability

A function is considered computable if it can be simulated by a Turing Machine. That is, there exists a Turing Machine that, when given a function’s input, produces the function’s output and halts. By the Church-Turing thesis, every effectively calculable function is computable, and hence has an equivalent Turing Machine.

Definition §

Computable (Function) ^def-computable-function

A function $f:X\to Y$ that operates over a finite set $X=\{x_1,\dots ,x_n\}$ is considered computable iff there exists a Turing Machine, $M$ such that, when given any $⟨x_i⟩$ as input, halts with $⟨f(x_1)⟩$ in its input tape.

• $⟨x_i⟩$ refers to the TM encoding of $x_i$
• To convert the function to a set (computability-wise), we ask the question, is there a TM $M$ that recognises the language $L=\{⟨x_1,f(x_1)⟩,⟨x_2,f(x_2)⟩,\dots \}$

Computable (Set) ^def-computable-set

A finite set $X=\{x_1,\dots ,x_n\}$ is considered computable iff its associated language, $L=\{⟨x_1⟩,⟨x_2⟩,\dots ⟨x_n⟩\}$ is T-Decidable

• $⟨x_i⟩$ refers to the TM encoding of $x_i$
• This also corresponds to decision problems.

This also means:

$$\text{Computability}⟺\text{Decidability}$$

and its complement:

$$\text{Undecidable Function}⟺\text{Uncomputable Functions}$$

Computable Numbers §

The definition of computability extends beyond functions. We can defined a computable number as any number that can be generated by a Turing Machine, $M$ after a finite amount of time. Informally, it means we can print the first $n$ digits of the number in finite time using $M$.

A computable number [is] one for which there is a Turing machine which, given $n$ on its initial tape, terminates with the $n$-th digit of that number [encoded on its tape].

• Marvin Minsky

#todo this appears to be wrong, see Cauchy representation of $x$ and this post: https://math.stackexchange.com/questions/4048442/wikipedias-definition-of-a-computable-numbers

For example, the number $3.14$ is computable by the Turing Machine below: %%🖋 Edit in Excalidraw, and the light exported image%%

#todo How to make a more optimised TM? and how to get it to have leadings 0’s after?

However, when we try to compute real numbers, we run into a problem. How do we compute $\pi$, which has infinite digits, using a finite number of states?

Uncountable Sets Are Not Computable §

Any uncountable set is not computable, simply because there are more elements in the set than there are Turing Machines.

The real numbers are uncountable, so most real numbers are not computable. The set of finitary functions on the natural numbers is uncountable, so most are not computable. Examples of such functions are Busy Beaver and the Kolmogorov complexity. #TOSEE