§1. Основные понятия и определения.
Алфавит, слова.
Введем понятие ленты, разделенной на равные участки, называемые ячейками или клетками. Будем считать ленту конечной в любой данный момент, но неограниченно надстраиваемой в обе стороны, так, что у каждой ячейки есть соседние справа и слева. Одно из возможных состояний ячеек будем называть исходным. Ячейки, находящиеся в этом состоянии, будем называть пустыми.
Произвольное конечное множество букв назовем алфавитом. Конечная последовательность ячеек, занятых некоторыми буквами назовем словом. Длиной слова называется число занятых ячеек. Пусть А, В – слова, записанные в алфавите, не содержащем самих символов А и В. Тогда АВ – слово, получающееся, если сначала выписать слово А, а затем приписать справа слово В. Слово АВ называется композицией (или произведением) слов А и В. Удобно ввести еще пустое слово, композиция которого с любым словом считается по определению равной этому последнему слову. Пустое слово не следует путать с пустой ячейкой.
Слово
А
называется подсловом
слова В,
если В
можно представить в виде
,
гдеС
и D
– некоторые (возможно пустые) слова.
Слово А
может входить несколько раз в слово В,
при этом говорят о первом, втором и т.д.
вхождении слова А
в слово В.
Функции. Термы.
Если некоторым элементам множества Х поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из множества X во множество Y. Множество тех элементов из Х, у которых есть соответствующие образы во множестве Y, называется областью определения функции, а те элементы из Y, которые соответствуют некоторым элементам из Х, называются множеством значений функции.
Если область определения функции совпадает с множеством Х, то функцию называют всюду определенной.
Две
функции f
и g
из Х
в Y
называются равными,
если они имеют одну и ту же область
определения и значения их совпадают в
каждой точке области определения.
Частичные функции из множества
во множествоY
называют частичными
функциями
от n
переменных или n-местными
функциями (частичными) из Х
в Y.
Частичная функция из прямого произведения
вХ,
называется n-местной
частичной
операцией
на Х.
Для записи различных выражений пользуются особым формальным языком. Алфавит этого языка состоит из символов трех групп.
Символы первой группы называются предметными символами. В качестве таких символов обычно употребляют буквы a, b, x, y, … или те же буквы с индексами.
Символы
второй группы называются функциональными,
будем их обозначать
,
и т.д. Буква
– n
– местный
функциональный символ. Верхний индекс
опускают, если известно, от какого числа
переменных этот функциональный символ
зависит.
Символы третьей группы – это левая и правая скобка и запятая.
Слова особого вида, записанные в этом алфавите, называются термами.
Термы
длины 1 – это однобуквенные слова,
составленные из букв, являющихся
предметными переменными. Далее пользуемся
индукцией. Пусть для некоторого
термы длины, меньшейS,
определены. Тогда слово длины S
называется термом, если оно имеет вид
,
где
- термы меньшей длины, а f
– это n
– местный функциональный символ.
Например, если а,
х – предметные
символы, а f,
g
– одноместный и двуместный функциональные
символы, то слова x,
f(a),
g(x,
a),
g(f(x),
g(a,
x))
являются термами длины 1, 4, 6, 14
соответственно.
По определению, задать значение предметного символа – это значит указать некоторое непустое множество, называемое основным множеством и сопоставить с рассматриваемым символом некоторый элемент этого множества, который называется значением данного символа.
Задать значение n-местного функционального символа – это значит сопоставить с ним какую-нибудь частичную n–местную операцию, определенную на основном множестве.
Теперь по индукции можно определить значение терма.
Если
в качестве значений функциональных
символов взяты частичные операции,
определенные не всюду на основном
множестве, то и значение терма может
оказаться неопределенным. При записи
термов пользуются сокращениями. Если,
например, x,
y
– предметные символы, f
– символ двуместной операции, то терм
f(x,
y)
обычно пишут в виде xfy.
В частности, если двуместные операции
обозначаются символами +, ,
-, то термы
,сокращенно
обозначают
.
Дальше всюду под числами понимаем 0 и
натуральные числа 0, 1, 2, 3, …
Множество
этих чисел будем обозначать N.
Частичные функции, определённые на
прямом произведении
,
направленные
в N
будем называть k-местными
числовыми частичными функциями.
Для краткости будем называть их просто
функциями.
Символы +, *, - будем считать двуместными
функциональными символами, фиксированными
значениями которых являются обычные
арифметические операции. Во множестве
натуральных чисел первые две операции
всюду определены, а операция вычитания
– частичная. Далее нам будут необходимы
следующие числовые функции
,
имеющие по определению следующие
значения:
,
,
.
Эти
функции будем называть простейшими.
Верхние индексы говорят, от какого числа
переменных эти функции зависят. Поэтому
вместо символов
,
будем писатьS,
O.
Результатом функции S
есть первоначальное число, увеличенное
на единицу. Функция О
обнуляет исходную числовую
последовательность. А последняя функция
J
выбирает из предъявленной числовой
последовательности число, стоящее на
определённом месте. Эти функции можно
комбинировать, получая более сложные
функции.
Кодирование.
Теория алгоритмов имеет дело со словами в конечном алфавите. Однако многие объекты нельзя рассматривать как слова в некотором алфавите. К таким объектам, например, можно отнести рациональные числа, алгебраические числа и т.д. Тем не менее, некоторые из таких объектов могут быть закодированы в подходящем конечном алфавите. Например, взяв алфавит из двух символов 0, 1, можно закодировать любое натуральное число, взяв его двоичную запись. При двоичном кодировании не всякое слово в алфавите 0, 1 служит кодом натурального числа (например, 001).