[документация]

История на Entscheidungsproblem - изчислимостта като проблем

1. Георг Кантор - въведен е методът на диагонализацията.

2. Хилберт търси обща алгоритмична процедура за решаване на математически проблеми. - 1900 - 1928 г.

3. Бъртранд Ръсел оповестява парадокса на множествата.

4. Курт Гьодел предлага своя теорема - всяка математическа система от аксиоми съдържа твърдения, които не са нито доказуеми, нито недоказуеми - 1931 г. Опитът на Хилберт се проваля.

5. Алонсо Чърч предлага твърдението, че всяка интуитивно изчислима f е рекурсивна функция. Чърч и Тюринг, независимо един от друг, достигат до сходни резултати: Функцията се счита за изчислима, ако може да бъде изчислена от Тюринг-машина.

6. Алън Тюринг прави опит за решение на проблема за изчислимостта и създава машината на Тюринг - 1937 г. Веднага възникават и проблемите за спирането на машината.