Кіріспе
Есептеу теориясындағы ұғым. Есептеу теориясындағы μ операторы, минимизация операторы немесе шексіз іздеу операторы, белгілі бір қасиеті бар ең кіші табиғи санды іздейді. μ операторын примитивті рекурсивті функцияларға қосу, барлық есептелетін функцияларды анықтауға мүмкіндік береді.
In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ operator to the primitive recursive functions makes it possible to define all computable functions.
Жалпы функциясын көрсету
Функция жалпы функция болу үшін міндетті түрде басқа әдіспен (мысалы, индукция) оның параметрлерінің әр комбинациясы үшін қандай да бір табиғи сан y μ операторын қанағаттандыратынын, сондықтан есептеуді білдіретін алгоритм аяқталуын көрсету керек: "Біз теңдеулер жүйесінің жалпы рекурсивті (яғни толық) функцияны анықтайтынына сену үшін әрқашан күдікпен қарауымыз керек. Әдетте, мұндай жағдайларда қосымша дәлелдерді қажет етеміз, мысалы, индуктивті дәлелдеме түрінде, әр аргумент мәні үшін есептеу бірегей мәнмен аяқталады." (Minsky (1967) p.186)
" 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)
"Басқаша айтқанда, функцияның жалпы (яғни толық) рекурсивті екендігі көрсетілген жағдайда ғана, оны тиімді есептеуге болады, егер оның жалпы рекурсивті екендігін дәлелдейтін әдіс тиімді болса." (Kleene (1952) p.319)
Бұл нені білдіретінін мысалы ретінде mu рекурсивті функциялардың мысалдарын қараңыз. Тіпті ең қарапайым қысқартылған шегеру алгоритмі "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) жағдайларының барлығы да күтілген нәтижені беретінін көрсететін "нақты дәлелдеме" ойлап тапқанша, мазасыздық сезімі тастамайды. Клине айтқандай: біздің "дәлелдемеміз" (яғни дәлелдеме ретінде қызмет ететін алгоритм) тиімді деп санауға жеткілікті сенімді ме?
(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?