A real computer is like an approximation of a Turing machine. ## Halting problem A Turing machine can have a decision problem saying, does the machine enters a state such that it has answer to our question. - if enters this state, we get an answer - if it never enters, then it keeps going forever and doesn’t halt. This makes a problem undecidable.