- related to turing test
- decision problem
- first order logic solution?
premises entail conclusion
is the problem going to give us an answer, or is it going to go on forever
will it halt or not
will it ever halt?
logical problem <> halting problem
impossible for a system to tell us whether a given machine and given input will ever halt or not
halting programs asks:
is it possible to write a program that determines whether another program halts?
proof by contradiction - proved by alan turing
that its not solvable
