Необходимые пояснения

Из трёх введённых понятий основным является полувычислимость, ибо вычислимость сводится к нему. Для выделения вычислимых функций из полувычислимых можно применить несколько методов, в частности использовать характеристические функции (x).

Существуют невычислимые функции, так как каждая программа – это конечный текст в конечном алфавите, так что множество программ счётно, тогда как множество всех функций отображения Z Z несчётно.

4.

На первый взгляд кажется, что приведённых определениях есть слабое место: не точно определено понятие «программы». Однако при любом уточнении программа суть текст над конечным алфавитом. Но есть «сильный» вопрос: возможно существует иерархия точно описываемых возрастающих по мощности вычислительных средств, таких что для каждой функции отображения Z Z можно подобрать свою программу, которая может вычислять эту функцию?

Фундаментальным открытием теории вычислимости было то обстоятельство, что на этот последний вопрос нужно дать отрицательный ответ.К настоящему времени математика обладает единственным и окончательным формальным понятием, которое выдержало все проверки на его соответствие интуитивному представлению о полувычислимости и именуется тезисом Чёрча в следующих формулировках…

«Слабейшая форма» тезиса (цитируется по работе Ю.И.Мамина)

Можно явно указать:

а) семейство простейших полувычислимых функций;

б) семейство элементарных операций, которые позволяют строить по одним полувычислимым функциям другие полувычислимые функции;

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

Нетрудно заметить, что приведённые выше понятия и определения подводят к понятию рекурсивной функции, к применению рекурсивных процедур. (Википедия: Реку́рсия — процесс повторения элементов самоподобным образом. В математике и информатике рекурсия имеет отношение к методу определения функций. Рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой.) Так и появилась «обычная форма тезиса Чёрча.

«Обычная форма» (цитируется по работе Ю.И.Мамина)

А) Функция f полувычислима, если и только если она частично рекурсивна.

Б) Функция f вычислима, если и только если f и частично рекурсивны.

(Здесь обозначено: D(f) – область определения функции f, а (x) – характеристическая функция, принимающая значение 1, если x X, либо значение 2, если x X)

«Конструктивно» (Вычислительные системы)

Тезис Чёрча – утверждение, согласно которому понятие вычислимости по Тьюрингу является корректной формализацией нашего интуитивного понятия эффективной вычислимости.