Cтраница 2
Основной тезис Тьюринга является аналогом уже знакомого нам тезиса Черча. Может показаться, что машины Тьюринга приводят к более широкому понятию вычислимости, чем рекурсивные функции. Но это не так, потому что буквы любого алфавита можно закодировать с помощью двух символов 1 и 2 ( метод такого кодирования описан в § 2 гл. [16]
Существуют как самоприменимые, так и несамоприменимые алгоритмы. Примером самоприменимого алгоритма является так называемый тождественный алгоритм в любом алфавите А, содержащем две или более двух букв. Этот алгоритм применим к любому слову р в алфавите А и перерабатывает любое входное слово в себя. [17]
Пост предложил иную алгоритмическую схему, которая характеризуется еще большей простотой. Это ограничение не влияет на ее универсальность, потому что любой алфавит, как известно, может быть закодирован двумя знаками. [18]
Сортировщик перфокарт конструируется для небольшого алфавита, А 10 или 12, что обычно соответствует десятичным цифрам. Алфавитные сортировки требуют дополнительных усилий. Поскольку вычислительная машина может иметь произвольное число бункеров, то теоретически может обрабатывать любой алфавит. Если алфавит большой, - найример, буквенно-цифровой набор BCD) имеет 64 символа - возникают проблемы в распределении памяти для бункеров. Сортировщик перфокарт обеспечивает фактически неограниченное количество памяти, так как можно удалять карты из карманов во время сортировки, и все стеки имеют неограниченные размеры. Вычислительная машина обязательно накладывает ограничения на размер области распределения. Если эта область расположена в основной памяти, то ограничением является доступный объем основной памяти. Попытки улучшить поразрядные методы в основном заключаются в сокращении объема требуемой памяти. [19]
Такая замена называется кодировкой. Каждой букве из первого алфавита ставится Е соответствие ее код, представляющий собой слово во втором алфавите. На самом деле, всегда достаточно иметь дело с алфавитом из двух букв, потому что любое слово из любого алфавита можно закодировать в алфавите из двух букв. [20]
Обратное ( что гораздо труднее) тоже верно. Из ( с) теперь следует, что ограниченная проблема соответствия над алфавитом A Q а, р при 90 неразрешима. Кодируя A J а, р двухбуквенным алфавитом ( см. следствие 6.1.2), мы получаем неразрешимость ограниченной проблемы соответствия ( а значит, и общей проблемы соответствия) над любым алфавитом, содержащим более одной буквы. [21]