Математическая логика и теория алгоритмов

A i { n ) = n +\ для любого натурального п. Алгоритм A t , как и Ао, не применим к пустому слову. Когда ярассмотрел то,чтонужно людям присчете, л нашел, чтовсеэтоесть чгюло. Аль-Хорезми § 4. Функции частично вычислимые и вычислимые по Маркову Напомним, что функция Дх) называется частично определеппой на множестве М , если значения этой функции определены не для всех X изМ. Функция / называется арифметической, если ее значения и зна­ чения ее аргументов являются целыми неотрицательными числами, т.е. область определения аргументов и область значений функции есть множество натуральных чисел. Положим, как ираньше, алфавитМ={1,*}. Пусть ф частично определенная арифметическая функция от п аргументов. Положим, что существует некоторый алгоритм (не обя­ зательно нормальный) Аср в алфавите М , позволяющий вычислять значения этой функции всякий раз, когда значение функции существует, т.е. ср(Ус1,А:2,..,Ус„) тогда и только тогда, когда хотя бы одна из частей этого равенства определена. При этом считаем, что алгоритм Лф не применим к словам, отличным ох с]юв вида (ki,k2,...,k,^ ). Назовем функцию ф частично вычислимой п оМ а р к о в у ф нкцией, если существует нормальный алгоритм В над М , вполне эквивалентный относительно алфавита М . Иными словами, и-архументная частично определеннш! функция ф частично вычислима по Маркову тогда и только тогда, когда 225