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?

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)

Uncomputability

1. Reduction from an undecidable problem
2. Rice Theorem

General guideline

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