Вообще, с этой терминологией время от времени кто-нибудь создаёт путаницу.
1) Начнём с того, что есть строгое математические понятия "частично-рекурсивная функция", определяемой в терминах операторов над частичными функциями из
в
. Оно было введено Клини и Чёрчем в начале XX века как попытка формализации того, что для функции существует алгоритм вычисления. В англоязычной литературе термин пишется так: "partially recursive function".
2) Формализация оказалась на удивление удачной. Было строго доказано, что функция частично-рекурсивна тогда и только тогда, когда она вычислима на машине Тьюринга. А машина Тьюринга, несмотря на свою кажущуюся простоту, позволяет моделировать все приемы программирования, известные человечеству вплоть до настоящего момента. Более того, не только не известно ни одного алгоритма, вычисляющего не частично-рекурсивную функцию, но ещё и совершенно непонятно, с какой стороны его можно пытаться искать.
3) В связи с тем, что на протяжении десятков лет никто так и не смог бросить тень сомнения на то, что каждая алгоритмически вычислимая функция (возможно, частичная, с как всегда стандартным соглашением: функция неопределена тогда и только тогда, когда вычисляющий его алгоритм никогда не заканчивает свою работу, то есть не останавливается), в настоящее время все математики свято верят в тезис Чёрча: для частичной функции из
в
существует алгоритм вычисления тогда и только тогда, когда эта функция частично рекурсивна.
4) По мере того, как математики всё более и более доверяли тезису Чёрча, его использовали всё чаще и чаще. Например, в типичной статье по теории вычислимости 1970-ых годов теорема о том, что некоторая функция является частично рекурсивной, доказывалась не через определение чрф, а простым описанием алгоритма её вычисления на естественном языке (английском, русском и т. д.) При этом алгоритмы оказывались всё более и более сложными, их описания могло растягиваться на десятки, а то и сотни страниц...
5) Наконец, в 1980-ых произошла смена терминологии. Поскольку ситуация сложилась так, что в журнальной, а потом и в книжной литературе определение частично-рекурсивной функции обычно никто даже и не вспоминал, а предметом исследования были вычислимые (в смысле алгоритмически вычислимые) функции, то решили, что их не стоит больше называть частично рекурсивными, а надо стараться называть вычислимыми (в смысле алгоритмически вычислимыми). Всё-таки термин чрф - это изначально очень специфический класс функций, который по счастливой случайности совпал с другим, гораздо более естественным классом. А коли мы уже давно интересуемся в первую очередь наличием алгоритма вычисления, то новая терминология будет подчёркивать этот момент, в отличие от старой, которая de facto его затушёвывала. На практике это означало замену слова "рекурсивный" на слово "вычислимой" во всех относящихся к теме терминах.
6) Однако со сменой терминологии связан один тонкий момент, о котором многие даже не подозревают. Вся эта наука лучше всего развита в англоязычных странах, так что термины обычно придумываются у них, а потом переводятся на русский для нас. И вот смотрите: когда в терминах было слово "рекурсивный", в соответствии с изначальными определениями это означало очень конкретную вещь. И термины выглядели так:
partially recursive function
recursive function = total recursive function
Два термина в последней строчке обозначают одно и то же, просто синонимы. Рекурсивная функция по определению есть всюду определённая частично рекурсивная функция, слово total подчеркивает всюду определённость, однако можно и не писать total, достаточно опустить наречие partially. На русский первая строчка переводилась как "частично-рекурсивная функция", а вторая "рекурсивная функция = общерекурсивная функция".
7) Теперь мы от этой устаревшей терминологии переходим к новой, которая по нашему замыслу должна лучше подчёркивать природу объектов. Мы говорим про функции, вычислимые алгоритмами. Эти функции в силу своей природы могут быть частичными, то есть, возможно, где-то не определёнными, ибо алгоритмы иной раз зацикливаются, и это зацикливание как раз и понимается как неопределённость. Посему, называя функцию вычислимой, естественно изначально считать её частичной. Так естественно, что про частичность можно и не писать. И появляются термины:
computable function = partial computable function
total computable function
Возможность быть где-то не определённой - естественна для вычислимой функции и вытекает прямо из определения. Её можно подчёркивать, написав дополнительно, что функция является partial, а можно и считать заданной по умолчанию. А вот всюду определённость у вычислимой функции - факт достаточно случайный, и еслим мы хотим его отметить, слова total уже никак не опустишь.
8) Обратите внимание на то, что в новой терминологии наречие partially стало прилагательным partial. И это естественно, ибо ведь сама функция является частичной, а не её вычислимость :)
9) И вот нашёлся, блин, какой-то дуболом, который, переводя на русский новую терминологию, начал использовать термины "частично-вычислимая функция", "вычислимая функция" и "всюду определённая вычислимая функция". Причём второй не как синоним первого, а как синоним третьего. А в первом - наречие вместо прилагательного. То есть просто взял старую терминологию и тупо заменил слово "рекурсивный" словом "вычислимый", не удосужившись даже внимательно прочитать оригинал. Один дуболом нашёлся, другой его скопировал, третий подхватил. И вот теперь в русскоязычных текстах сплошь и рядом можно встретить результаты этого невнимательного перевода. Корявые с точки зрения передачи смысла, а в одном месте так просто преступные, ибо "вычислимая функция" - это не то же самое, что "computable function". "Вычислимая функция" = "total computable function", а "computable function" = "частично-вычислимая функция".
10) И, наконец, чтобы окончательно добить моё тонкое и нежное чувство стиля, русские стали пользоваться сокращением чвф. Вчера вот, например, мой коллега, принимал при мне пересдачу и говорил студенту: "Дайте, пожалуйста, определение чвф". И ждёт от него исходного определения чрф в духе Чёрча-Клини. Мне аж пришлось отвернуться, чтоб никто не видел, как меня от этого чвф перекосило.
11) Сам я, по возможности, стараюсь использовать в своих статьях адекватный перевод англоязычных терминов. То есть вычислимая функция у меня может быть частичной, а если нет, то она снабжается эпитетом "всюду определённая". Если хочу подчеркнуть частичность, пишу прилагательное, а не наречие. Однако, поскольку традиция дурного и неправильного перевода уже успела получить достаточно широкое распространение, в начале каждой статьи приходится уточнять, в каком смысле я использую термины.
12) Для студентов решил оставить старую терминологию. Всё-таки в курсе мы начинаем с того, что вводим старые, изначальные определения Чёрча-Клини. Про новую терминологию упоминаю, однако во избежание перегруза студенческих мозгов до конца курса стараюсь пользоваться старыми терминами. Иногда, забываясь, непроизвольно соскакиваю на новые.
вычислимо перечислимо
В популярных книжках упоминаются паркеты на плоскости его имени.