Курт Гедель

По определению функции, вычисляемые «машиной Тьюринга», являются «вычислимыми», поэтому
инструкции по их вычислению могут быть переданы разным машинам без опасения, что возникнут ошибки
или неясности. Вместе с тем существуют функции, не поддающиеся вычислению, более того, они
составляют подавляющее большинство, хотя трудно дать определение такой функции. Как ни странно, но
пример невычислимой функции следует прямо из теории «машины Тьюринга». Присвоим значение
«единица» целому числу, соответствующему нормально работающей машине; «нуль», напротив, будет
соответствовать машине, вошедшей в режим безостановочных повторных вычислений. Таким образом мы
задали невычислимую функцию, и доказательство этого повторяет доказательство, данное Геделем для
логических систем. Зная эту функцию, мы можем сказать заранее, не прибегая к запуску в работу самой
программы, остановится ли соответствующая машина или будет работать вхолостую.

---

Другие статьи по теме:

- Альберт Эйнштейн
- Галилео Галилей
- Джеймс Кларк Максвелл
- Курт Гедель

Это интересно:

Новости космоса: