КАНОНИЧЕСКИЕ УРАВНЕНИЯ АВТОМАТА

26Вычислимые функции и их алгоритмы

вычислимой называется функция от одного или нескольких натуральных аргументов, натуральные значения которой получаются в результате выполнения некоторого алгоритма. Определить термин "алгоритм" без синонимичных ссылок на себя же самого сложно. Фразы типа "дискретные, однозначные последовательные действия..." не являются полностью удовлетворительными. Поэтому считается, что "алгоритм", как и "множество" — это понятие первичное. Для определённости будем считать, что алгоритм это математическая модель уже существующего физического устройства — цифрового компьютера. У него идеализируется память, которая может быть сколь угодно большой. Естественно, исключаются и форс-мажорные ситуации - перегрев, блондинки, чашки с кофе и т.п. Поэтому вычислимой будет функция, для которой можно составить программу, т.е. дать конечное определение, позволяющее вычислить функцию при помощи этого идеального устройства.

Программа — это конечная строка символов из некоторого, опять же конечного алфавита. Компьютер имеет вычислитель (маркер), который однозначным образом перемещается по строке (тексту программы). Это перемещение не обязательно линейно, и при достижении некоторого символа возможен переход на несколько символов вперёд или назад.

Таким образом есть программа (строка " ") и вычислитель (маркер), который на данном шаге выполнения алгоритма указывает на один символ — инструкцию для компьютера (на рисунке выше это треугольник, стоящий на инструкции " ").

Программы записываются на некотором формальном языке программирования. Это может быть язык машины Тьюринга, ассемблер для процессоров с бесконечной разрядностью, или С++, в котором нет ограничения на размер целочисленных переменных. Формальный язык определяется при помощи синтаксических правил. Это означает, что всегда можно отличить "бессмысленную" последовательности символов от тех, по которым может перемещаться вычислитель. Ситуация полностью аналогична, например, арифметике, где правильно построенная формула " " отличима от неправильной: " ".

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

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

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

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

Функция — это "ящик" с несколькими входами , и одним выходом :

Фразы "один вход" или "один выход" не являются принципиальными. Понятно, что упорядоченных целых чисел всегда можно представить как одно, и наоборот. Для этого достаточно взять первых простых чисел и вычислить . Обратная операция разложения на простые множители одного числа позволяет восстановить значения всех . Тем не менее, будем считать, что может быть несколько входов, но выход всегда один.

Понятие конструктивного объекта

Сло­жи­лось пред­став­ле­ние, что в ка­че­ст­ве ис­хо­дных дан­ных и ре­зу­ль­та­тов ал­го­рит­ма мо­гут вы­сту­пать не лю­бые объ­е­к­ты. Ал­го­рит­мы мо­гут иметь де­ло то­ль­ко с ком­би­на­ци­ями зна­ков. Объ­е­к­ты, над ко­то­ры­ми "ра­бо­та­ет" ал­го­ритм, обыч­но на­зы­ва­ют кон­стру­к­тив­ны­ми. По­ня­тие "кон­стру­к­тив­ный объ­ект" - это не­фор­ма­ли­зо­ван­ное, ин­ту­итив­ное по­ня­тие, его фор­ми­ро­ва­ние свя­за­но с раз­ли­че­ни­ем кон­стру­к­тив­но­го и не­кон­стру­к­тив­но­го в ма­те­ма­ти­че­с­ком мыш­ле­нии. По­яс­не­ние то­го, что сле­ду­ет по­ни­мать под кон­стру­к­тив­ным объ­е­к­том да­ли В.А.Успенский и А.Л.Семёнов [1987]: это "та­кой объ­ект, ко­то­рый мо­жет быть на­бран весь це­ли­ком и пред­став­лен нам для рас­смо­тре­ния". Кон­стру­к­тив­ный объ­ект до­лжен быть ко­неч­ным (в ин­ту­итив­ном по­ни­ма­нии это­го сло­ва) и со­став­лен­ным из ко­неч­но­го чис­ла от­де­ль­ных эле­мен­тов, каж­дый из ко­то­рых при­над­ле­жит од­но­му из ко­неч­но­го чис­ла ти­пов. Од­на­ко, кон­стру­к­тив­ный объ­ект - это не про­сто ко­неч­ное мно­же­ст­во эле­мен­тов. Кон­стру­к­тив­ный объ­ект до­лжен иметь, кро­ме то­го, не­ко­то­рую внут­рен­нюю сис­те­му ко­ор­ди­нат, по­зво­ля­ющую одно­знач­но ло­ка­ли­зо­вать лю­бой его эле­мент (вто­рой эле­мент спра­ва, эле­мент пя­той стро­ки и тре­ть­е­го стол­бца и т.д.).

При­ме­ра­ми кон­стру­к­тив­ных объ­е­к­тов слу­жат сло­ва в ал­фа­ви­те. Час­тны­ми ви­да­ми слов, оче­вид­но, яв­ля­ют­ся фор­му­лы фор­ма­ль­ных язы­ков, за­пи­си на­ту­ра­ль­ных, це­лых чи­сел в g-ич­ной сис­те­ме счис­ле­ния, за­пи­си ра­ци­она­ль­ных чи­сел в ви­де обык­но­вен­ных дро­бей, ко­неч­ные де­ся­тич­ные дро­би, мно­го­чле­ны с ра­ци­она­ль­ны­ми ко­эф­фи­ци­ен­та­ми (в том слу­чае, ес­ли их ко­эф­фи­ци­ен­ты за­пи­са­ны в ви­де слов). Кон­стру­к­тив­ны­ми объ­е­к­та­ми яв­ля­ют­ся так­же ко­неч­ные мат­ри­цы слов и бу­ле­вы фун­кции.

Сло­ва в ал­фа­ви­те (ко­неч­ные по­сле­до­ва­те­ль­но­сти сим­во­лов) - удач­ный вид кон­стру­к­тив­ных объ­е­к­тов, по­ско­ль­ку сов­ре­мен­ные ком­пь­ю­те­ры чи­та­ют и об­ра­ба­ты­ва­ют ин­фор­ма­цию, во­об­ще го­во­ря, по­сим­во­ль­но и по­сле­до­ва­те­ль­но. По­сле­до­ва­те­ль­ные одно­мер­ные за­пи­си при­вы­чны и для че­ло­ве­ка. Кро­ме то­го, ин­ту­итив­но яс­но, что вся­кий кон­стру­к­тив­ный объ­ект мож­но одно­знач­но и пол­нос­тью опи­сать или за­ко­ди­ро­вать в ви­де сло­ва, и на прак­ти­ке это всег­да уда­ет­ся. В си­лу это­го, имен­но сло­ва в ал­фа­ви­те яв­ля­ют­ся глав­ным ви­дом кон­стру­к­тив­ных объ­е­к­тов. По­это­му обыч­но огра­ни­чи­ва­ют­ся изу­че­ни­ем ал­го­рит­мов, у ко­то­рых ис­хо­дные дан­ные и ре­зу­ль­та­ты яв­ля­ют­ся не­пус­ты­ми сло­ва­ми. Ра­зум­но так­же со­об­ра­же­ние о том, что ис­пол­ни­тель ал­го­рит­ма мо­жет раз­ли­чать лишь ко­неч­ное чис­ло ис­хо­дных сим­во­лов, по­это­му в ка­че­ст­ве мно­же­ст­ва до­пус­ти­мых дан­ных ал­го­рит­ма и об­лас­тей ре­зу­ль­та­тов рас­смат­ри­ва­ют лишь мно­же­ст­ва слов в ко­неч­ных ал­фа­ви­тах.

Впро­чем, сле­ду­ющее утвер­жде­ние по­ка­зы­ва­ет, что в не­ко­то­ром смыс­ле до­ста­то­чно ис­сле­до­вать то­ль­ко те ал­го­рит­мы и со­от­ве­т­ст­ву­ющие вы­чис­ли­мые фун­кции, у ко­то­рых в ка­че­ст­ве ис­хо­дных дан­ных и ре­зу­ль­та­тов ис­по­ль­зу­ют­ся то­ль­ко на­ту­ра­ль­ные чис­ла (точ­нее, их за­пи­си).

За­ну­ме­ру­ем эле­мен­ты про­из­во­ль­но­го ко­неч­но­го ал­фа­ви­та A«{a0,a1,...,ap-1}.

Пусть A+ - мно­же­ст­во всех не­пус­тых слов в ал­фа­ви­те A, wÎA+. Тог­да для не­ко­то­рых k0,k1,...ksÎ{0,1,...,p-1}

w=ak ak ...ak (*)
0 1 s