Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
р'-'вРо (г0<Я).
Таким образом, период р' также будет содержать только простые множители, не превосходящие Я. Теорема доказана.
На основе этих утверждений мы докажем следующий факт.
Теорема 18. Система (Р0Д1 С) не имеет конечного базиса.
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
ИЗ
Доказательство. Пусть имеет место противное, т. е. система {Род, ь, С) обладает базисом Д, ..Д. Обозначим через г1? ..., г, веса о.-д. функций Д, ..Д. Пусть, далее,
г*-тах(г,, г.)
и р *— простое число такое, что р > г. Рассмотрим о.-д. функцию Д(Х), которая принимает значение, тождественно равное 7, где 7 — периодическая последовательность с периодом р, имеющая вид
? = 0,,, 010, ,.01,.,
V V
Функцию Д(ЙГ) нельзя выразить при помощи суперпозиции через функции Д, ..., Д. В самом деле, если /(Аг)—
произвольная суперпозиция функций /......... Д, то она
будет преобразовывать последовательность 0*=(0, 0, ...) (ее период равен 1) в последовательность периодическую с периодом, не содержащим простые множители, большие чем г. В то же время Д (0) = 7 — периодическая последовательность с периодом р > г. Мы пришли к противоречию. Теорема доказана.
Так как система (Род, к, С, О) имеет конечный базис, а (РСд, ь, С) конечного базиса не имеет, то операция О является существе иной.
В то же время система (Род, О) по очевидным соображениям не имеет конечного базиса, поэтому операция С является также существенной.
Глава 4
ВЫЧИСЛИМЫЕ ФУНКЦИИ § 1. Машины Тьюринга
Из предыдущего следует, что о.-д. функцию f(xi, ,.. ..., хп) можно задать при помощи канонических уравнений
2(«)-?(Х(г), <?((-1)),
С(0)-0.
Эти уравнения позволяют строить по входной последовательности значений переменных хи ..., хп выходную последовательность, Более того, значения выходной после-
8 С. В. Ябдонский
Ш Ч. I ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
допательности находятся постепенно по мере поступления входных значепий. Это позволяет трактовать выписанные выше уравнения как описание работы некоторого
дискретного преобразователя или автомата (рис. 1), который обладает г состояниями (г — вес о.-д. функции) и работает дискретно во времени, формируя состояние памяти и выходпое значение в момент времени ? но состоянию памяти в момент времени ? — 1 и входным значениям в момент времени ? в соответ-
Рис- * ствии с каноническими уравнениями.
Данное устройство, в отличие от реальных автоматов (автоматических устройств), никогда пе заканчивает работы. Можпо ввести другую функциональную характеристику, эквивалентную исходной, но имеющую финитный характер. Из детерминированности фупк-ции / вытекает, что отображение / порождает отображение конечных последовательностей вида (а(1), ..ос (г')} в конечные последовательности (у(1), . -7(0^ (*™
2, ...). Это отображение обозначим через ф(х). Функцию ф можно задать при помощи тех же канонических уравнений, что и /. Очевидно, что по функции ф(х) полностью восстанавливается функция /(ж) (в этом смысле выше говорилось об эквивалентности ф и /). Класс функций ф(х) обозначим через Р0Ят Функцию ф(ж) можно
интерпретировать как описание работы автомата в следующем смысле: в моменты времени 1, 2, ..г на вход поступают символы а{1), а(2), ..а(?), а на выходе получают символы у(1)> К (2), 7(0*» в последующие
моменты времени на вход ничего не поступает и автомат прекращает работу.
В этом случае отсутствие информации на входе равносильно тому, что входной последовательности {«(1), ... ..а(?)} соответствует бесконечная последовательность
М1) а (О, Л,
где Л — дополнительный символ входпого алфавита, означающий отсутствие информации. Появление на входе символа Л является условием останова устройства, т. е. появления на выходе последовательности
<т(1). ???» 7(0» л,
Введенные нами устройства, работающие над конечными входными последовательностями, можно трактовать
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
115
также в виде «машины». О па состоит из бесконечной вправо лепты и автомата (см. рис. 2). Бесконечная лента разделена па ячейки, которые нумеруются натуральными числами 1, 2, ..в ячейки 1, 2, ..., г вписываются символы а{1), а (2), ..а (г) из алфавита (0, 1, N—1).
Автомат обладает, головкой и может находиться в одном
11
i
\аШ |
лента
голодна
абтомат
Рис. 2
из (конечного числа) состояний хь ..хг. Головка в каждый из моментов времени t (?=1, 2, ...) обозревает одну ячейку ленты (при t = 1 обозревается 1-я ячейка); по символу, прочитанному на ленте, и но внутреннему состояиию автомат вырабатывает новое состояние и некоторый символ, который через головку вписывает в ту же ячейку (в начальный момент t~ 0 состояние автомата есть х,). После этого головка сдвигается по ленте па одну ячейку вправо и т. д. Машина останавливается при появлении в поле зрения головки символа А, и на ленте в ячейках -1, 2, ..i получается выходная последовательность {^{l), 7(2), 7(0^- Работу этой машины можно
задать при помощи так называемой программы, т. е. специальной таблицы (см. табл. 1).
В данной таблице строки занумерованы символами А, 0, 1, ..Ат—1, а столбцы—символами хь хг. Строка, соответствующая символу А, оставляется незаполненной. В клетку, расположенную в строке а (а#1 А) и в j-м столбце, вписывается тропка символов
