Классика баз данных - статьи

       

Вычислительная полнота


В [1] утверждается, что именно вычислительная полнота Tutorial D делает этот язык неразрешимым:

Если некоторый язык включает логику предикатов и является вычислительно полным, то логическим следствием является неразрешимость некоторых выражений этого языка [курсив добавлен].

Так что же означает вычислительная полнота языка?

Как это не странно, я не смог найти определение термина вычислительная полнота ни в одном из большого числа просмотренных мной литературных источников из компьютерной области. Но во многих из них имеется определение вычислимой функции, и я думаю, что достаточно разумно считать язык вычислительно полным в том и только в том случае, если в нем поддерживается вычисление всех вычислимых функций. Так или иначе, я буду использовать это в качестве рабочего определения. Так что же такое вычислимая функция? Вот пара определений из литературных источников:

  • Вычислимой функцией называется функция, которая может быть вычислена машиной Тьюринга за конечное число шагов [11].
  • Вычислимая функция – это функция, которую можно закодировать с использованием циклов WHILE [12].



Содержание раздела