To speak theoretically about whether tasks are computable or complex to solve by a machine, we need to define what machine we are talking about!

Turing machine

Turing machine is the universally accepted model for computation

Now that we have the model, we can better define computability and complexity

Computability

A task/language is computable/decidable in time $T$ if there exists a TM that calculates/decides it in $T(|x|)$ steps.

Machines as strings

• We know from Binary encoding that everything can be encoded in binary
• So TMs can also be encoded as binary strings

UTM: Universal Turing Machine

• Now that TMs can be encoded as binary strings, they can be given as input to other TMs!
• So let's build a simulator that gets the binary encoding of a TM $m$ and a string $x$, simulates the running $m$ over $x$ and returns the result.
  • Like a python interpreter
• This simulator exists and it's called a UTM.
  • Simulating the TM is obviously slower than running it directly.
  • If TM runs in $T$ time, the best UTM simulating TM runs in $C.T.log(T)$

Uncomputability

Uncomputable functions exist!

How to prove?

How to prove that a task is computable or uncomputable?

Proving Computability

1. Construct a TM that solves it!
2. Write an algorithm in pseudocode! Keep in mind that all steps must be elementary (or known to be computable)

Proving Uncomputability

1. Reduction from an undecidable problem
2. Rice Theorem

General guideline

1. Check if it's possible to write a python code to solve it -> decidable
2. Use Rice Theorem if it's a semantic language:
   1. if It's trivial -> decidable
   2. if non trivial -> undecidable
3. Check if you can reduce the halting problem to it