- Машина Тьюринга
- (Бильгаева Н.Ц.
- Теория алгоритмов, формальных
- языков, грамматик и автоматов)
- Восходит к Давиду Гильберту
- На рубеже 20 века сформулировал мировую проблему:
- Можно ли построить алгоритм, создающий необходимый алгоритм к любой, точно поставленной задаче?
- Такая постановка задачи неразрешима, т.к. фактически проблема сводится к логическому парадоксу брадобрея: Он бреет тех, кто не бреется сам. Если брадобрей бреется сам, то он принадлежит множеству тех жителей города, кто бреется сам, Но в объявлении утверждается, что наш брадобрей никогда не бреет тех, кто входит в это множество. Следовательно, наш брадобрей не может брить самого себя (Бертран Рассел)
Достарыңызбен бөлісу: |