Введение
Понятие в теории вычислимости
В теории вычислимости оператор μ, оператор минимизации или оператор неограниченного поиска находит наименьшее натуральное число, обладающее заданным свойством. Добавление оператора μ к примитивным рекурсивным функциям позволяет определить все вычислимые функции.
Демонстрация общей функции
Если функция должна быть тотальной, необходимо продемонстрировать каким-либо другим методом (например, индукцией), что для каждой комбинации значений ее параметров xi найдется некоторое натуральное число y, удовлетворяющее оператору μ, чтобы алгоритм, представляющий вычисление, мог завершиться: "мы всегда должны проявлять осторожность, предполагая, что система уравнений действительно определяет тотальную (т.е. общую) рекурсивную функцию. Обычно для этого требуются дополнительные доказательства, например, индуктивное доказательство того, что для каждого значения аргумента вычисление завершается единственным значением" (Minsky (1967) с.186). "Иными словами, мы не должны утверждать, что функция эффективно вычислима только на том основании, что она показана как тотальная рекурсивная, если демонстрация ее тотальности не является эффективной" (Kleene (1952) с.319).
" we must always hesitate to assume that a system of equations really defines a general recursive (i. e. total) function. We normally require auxiliary evidence for this, e. g. in the form of an inductive proof that, for each argument value, the computation terminates with a unique value." (Minsky (1967) p.186)
"In other words, we should not claim that a function is effectively calculable on the ground that it has been shown to be general (i. e. total) recursive, unless the demonstration that it is general recursive is effective. "(Kleene (1952) p.319)
For an example of what this means in practice see the examples at mu recursive functions—even the simplest truncated subtraction algorithm "x y = d" can yield, for the undefined cases when x < y, (1) no termination, (2) no numbers (i. e. something wrong with the format so the yield is not considered a natural number), or (3) deceit: wrong numbers in the correct format. The "proper" subtraction algorithm requires careful attention to all the "cases"
(x, y) = {(0, 0), (a, 0), (0, b), (a≥b, b), (a=b, b), (a<b, b)}. But even when the algorithm has been shown to produce the expected output in the instances {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, we are left with an uneasy feeling until we can devise a "convincing demonstration" that the cases (x, y) = (n, m) all yield the expected results. To Kleene's point: is our "demonstration" (i. e. the algorithm that is our demonstration) convincing enough to be considered effective?
В качестве примера того, что это означает на практике, обратитесь к примерам, касающимся μ-рекурсивных функций – даже самый простой усеченный алгоритм вычитания "x – y = d" может, для неопределенных случаев, когда x < y, выдавать (1) отсутствие завершения, (2) отсутствие чисел (т.е. ошибка в формате, из-за которой результат не считается натуральным числом) или (3) обман: неверные числа в правильном формате. "Правильный" алгоритм вычитания требует внимательного рассмотрения всех "случаев": (x, y) = {(0, 0), (a, 0), (0, b), (a≥b, b), (a=b, b), (a<b, b)}. Но даже если алгоритм показал ожидаемый результат для случаев {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, у нас остается ощущение неуверенности, пока мы не сможем разработать "убедительное доказательство" того, что случаи (x, y) = (n, m) также дают ожидаемые результаты. По мнению Клини: достаточно ли наша "демонстрация" (т.е. алгоритм, который служит нашей демонстрацией) убедительна, чтобы считаться эффективной?
" we must always hesitate to assume that a system of equations really defines a general recursive (i. e. total) function. We normally require auxiliary evidence for this, e. g. in the form of an inductive proof that, for each argument value, the computation terminates with a unique value." (Minsky (1967) p.186)
"In other words, we should not claim that a function is effectively calculable on the ground that it has been shown to be general (i. e. total) recursive, unless the demonstration that it is general recursive is effective. "(Kleene (1952) p.319)
For an example of what this means in practice see the examples at mu recursive functions—even the simplest truncated subtraction algorithm "x y = d" can yield, for the undefined cases when x < y, (1) no termination, (2) no numbers (i. e. something wrong with the format so the yield is not considered a natural number), or (3) deceit: wrong numbers in the correct format. The "proper" subtraction algorithm requires careful attention to all the "cases"
(x, y) = {(0, 0), (a, 0), (0, b), (a≥b, b), (a=b, b), (a<b, b)}. But even when the algorithm has been shown to produce the expected output in the instances {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, we are left with an uneasy feeling until we can devise a "convincing demonstration" that the cases (x, y) = (n, m) all yield the expected results. To Kleene's point: is our "demonstration" (i. e. the algorithm that is our demonstration) convincing enough to be considered effective?