Сведение алгоритмов к числовым функциям. 
Понятие вычислимой функции

Примером простейших конструктивных объектов являются слова в некотором абстрактном алфавите.

Алфавит (абстрактный) — это произвольное непустое конечное множество V = {а, 6, с,…}, элементы которого называют буквами или символами.

Словом (цепочкой) называют произвольную последовательность букв алфавита. Количество букв в некотором слове s называется длиной слова и обозначается s.

Пример 9.2. Пусть V = {0,1,2,3,4,5,б, 7,8,9, +,-}. Примерами слов в алфавите V будут 6*i = +1, $ 2 = —54 -I- 6, $з = 12 100. ?

Буквы (символы) и слова всегда стоит понимать в рамках некоторого алфавита. Так, если алфавитом являются отдельные слова в обычном понимании, а также символ «пробел» и знаки препинания, то словом в таком алфавите будет считаться предложение естественного языка.

Считается, что во множестве всех слов любого алфавита присутствует так называемое нулевое (пустое) слово Л, для которого |А| = 0 (слово нс состоит ни из каких символов).

Следует отметить тот факт, что при выборе подходящей формы записи конструктивные объекты могут быть представлены словами в некотором конечном алфавите.

Пример 9.3. Единичная матрица порядка 3 может быть записана в виде слова.

В общем случае произвольная целочисленная матрица размерности т х п может быть записана в подобном виде с использованием алфавита.

(здесь в качестве разделителей букв использован символ «;», чтобы отличать букву «,» от разделителя). ?

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

• 1. Пусть буквам алфавита V = {г?х, г/2,…, v_n} присвоены номера 1,2, …, п соответственно; пустое слово имеет помер 0.
• 2. Поставим в соответствие некоторому слову д = v_i2. .Vi_k, не содержащему пустого символа, лексикографический номер

Нетрудно заметить, что вычисление номера слова схоже с записью целого числа в системе счисления с основанием п, за исключением того, что никакая «цифра» it, гг, г к нс может быть нулем.

3. Для нахождения слова в алфавите по его номеру N нужно представить номер в виде N = pin + q₀, где 1 ^ 0 ^ п. Если pi < гг, то искомое слово состоит из символов с номерами puqo- Иначе продолжить разложение числа р — Р2П + Ч2-> где 1 ^ q-2 ^ п. При этом N = р₂п² + q ^l + qon°. Если р₂ ^ п, искомой цепочкой будет слово, составленное из символов р₂, qi, qo- В противном случае процесс разложения продолжается. Разложение выполняется до тех пор, пока очередное р_т не окажется меньше или равным п.

Пример 9.4. Пусть дай алфавит V3 = {а, 6, с, d}. Найдем:

• — лексикографический номер слова cabdca;
• — слово, соответствующее номеру 235.

Решение. В нашем случае п — 4 (алфавит содержит 4 символа), порядковыми номерами а, 6, с, d будут числа 1,2,3,4 соответственно. Произведем вычисления для слова cabdca по формуле (9.1):

Таким образом, лексикографическим номером слова cabdca будет 3533. Для нахождения слова по номеру 235 выполним разложение.

Таким образом, номеру 235 соответствует строка, символы которой имеют номера символов алфавита 3,2,2,3 (слева направо) соответственно, т. е. искомой строкой будет ebbe. ?

Очевидно, множество слов в произвольном конечном алфавите является счетным.

Пусть входом некоторого алгоритма является множество конструктивных объектов (ai, a2,. •, а*), имеющих лексикографические номера ПьП2,…, щ соответственно, а на выходе получен конструктивный объект у, составленный из символов того же алфавита. Так как у соответствует некоторому слову, то у так же будет иметь некоторый лексикографический номер п_у.

Между натуральными числами и конструктивными объектами имеется взаимно однозначное соответствие: для произвольного конструктивного объекта в некотором алфавите всегда можно указать его порядковый номер и наоборот. Поэтому работу алгоритма можно рассматривать таким образом, что набору натуральных чисел {ть, 71*2"• • •, rik) ставится в соответствие число п_у.

Данное определение напоминает определение числовой функции f (x 1, х₂,…, х^) в математическом анализе, когда набору аргументов (ад, #2, • • •, ад) ставится в соответствие некоторое значение. Это приводит к следующей точке зрения на понятие алгоритма.

Алгоритм это вычисление некоторой функции f (xi, ж₂,…, ад.), определенной на множестве натуральных чисел N.

Под областью определения функции / понимают множество X, состоящее из всех наборов (a;i, x₂, • • •, ад), для которых существует значение функции. Множество всех значений функции / называют областью значений.

Если существует некоторый алгоритм А, вычисляющий функцию f (x 1, #2,…, ад), то эта функция называется вычислимой. В этом случае говорят также, что «алгоритм А вычисляет функцию /».

На практике вычислимость функции алгоритмом означает следующее:

• 1. Если на вход алгоритма А поступает набор аргументов (ад, ад,…, ад) из области определения функции /, то алгоритм останавливается и выдает результат f (Xi, X₂,…, Xk).
• 2. Если на вход алгоритма А поступает набор аргументов вне области определения функции /, то алгоритм работает бесконечно (в теории, математически; на практике бесконечности нс допускаются) или останавливается без выдачи результата.

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