Heuristics, Undecidability and Simulation

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal, but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs. For example: is the number even?

An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.

An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve ALL instances of the problem.

Alan Turing, considered by many to be the father of computer science, proved that undecidable problems exist.

Computer simulation is the process of mathematical modeling, performed on a computer, which is designed to predict the behavior of, or the outcome of, a real-world or physical system.

Simulations often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world.

Simulations are most useful when real-world events are impractical for experiments: too big, too small, too fast, too slow, too expensive, or too dangerous.

For example, instead of letting an untrained pilot fly an actual plane, the pilot can learn by using a flight simulator.