Wstęp historyczny

Chronologiczny schemat ważnych wydarzeń:
1900 - na Międzynarodowym Kongresie Matematyków w Paryżu, D.Hilbert przedstawia 23 zagadnienia dotyczące podstawowych, według niego, kierunków badań matematycznych, które do dzisiaj przyciągają uwagę matematyków całego świata.
1928 - D.Hilbert przedstawia problem rozstrzygalności - "Entscheidungsproblem" - rozsrzygalność to właściwość problemu matematycznego, która decyduje o możliwości lub braku możliwości jego rozwiązania. Nie powstał jeszcze algorytm, który potrafi rozwiązać problem rozstrzygalności.
1930 - Alonzo Church i Stephen Cole Kleene wprowadzają rachunek λ(lambda). Ma on bardzo istotne zastosowanie w algorytmice: wszystkie algorytmy, które dadzą się zapisać w rachunku lambda, dadzą się zaimplementować na maszynie Turinga i odwrotnie.
1970 - Jurij Matijasiewicz wykazał, że 10 problem D.H. jest nierozstrzygalny.