Вычислительная полнота
В [1] утверждается, что именно вычислительная полнота Tutorial D делает этот язык неразрешимым:
Если некоторый язык включает логику предикатов и является вычислительно полным, то логическим следствием является неразрешимость некоторых выражений этого языка [курсив добавлен].
Так что же означает вычислительная полнота языка?
Как это не странно, я не смог найти определение термина вычислительная полнота ни в одном из большого числа просмотренных мной литературных источников из компьютерной области. Но во многих из них имеется определение вычислимой функции, и я думаю, что достаточно разумно считать язык вычислительно полным в том и только в том случае, если в нем поддерживается вычисление всех вычислимых функций. Так или иначе, я буду использовать это в качестве рабочего определения. Так что же такое вычислимая функция? Вот пара определений из литературных источников:
- Вычислимой функцией называется функция, которая может быть вычислена машиной Тьюринга за конечное число шагов [11].
- Вычислимая функция – это функция, которую можно закодировать с использованием циклов WHILE [12].
