Введение. 
Машина Тьюринга и невычислимые функции

Алан Тьюринг окончил Кембриджский университет в 1935 г. В это время внимание многих математиков было приковано к работам, посвященным логическим основам математики. Её фундаментальные понятия подверглись тщательному изучению и обоснованию. Особенно те, которые традиционно использовались без уточнения их смысла, на интуитивном уровне.

Алгоритм — одно из таких понятий. А. Тьюрингу удалось дать определение понятия «алгоритм». В качестве уточнения понятия он предложил некоторую гипотетическую конструкцию — машину, получившую вскоре название «машина Тьюринга». Он сделал свое изобретение в 1937 г. В то время Тьюринг стажировался в Принстонском университете в США. В Англию он вернулся знаменитым ученым.

Долгие годы А. Тьюринг работал в Манчестерском университете. Его конструкция начала свою вторую жизнь после создания ЭВМ, для которых понятие алгоритма — центральное. В 1951 г. Тьюринг стал членом Королевского общества Великобритании. В этот период он активно занимался теоретическими проблемами программирования, строил интерпретаторы для новых ЭВМ. Тьюринг ввел в научный оборот понятие стека и сделал значительный вклад в технологию программирования. В последние годы жизни А. Тьюринг живо интересовался математической биологией, на которую возлагал большие надежды.