Cтраница 2
Нумерация, или кодирование, программ, и особенно их эффективность, играют фундаментальную роль в теории вычислимости. [16]
Результаты, доказывающие, что одну задачу можно преобразовать в другую, являются общими в математической логике и теории вычислимости, но такие результаты сильно отличаются по духу от тех, которые представлены здесь. [17]
Два результата, с которыми мы встретились в этом разделе - - это типичные отрицательные результаты, составляющие часть теории вычислимости. [18]
Знаменитая теорема Геделя о неполноте [1931] предстг ляет собой один из многих результатов о формальной арифи тике, в котором теория вычислимости и логика тесно nepenj таются друг с другом. Полные доказательства этих утверж ний выходят за рамки настоящей книги. [19]
Значительный интерес представляет задача выявления разрешимых и неразрешимых проблем; последние, среди прочего, указывают на ограничения, возникающие в теории вычислимости, и тем самым демонстрируют теоретические границы возможностей реальных вычислительных машин. [20]
Учебник, в чем-то ведущий свое начало от работ по сетям Мак-Калока - Питтса, который все еще остается прекрасной работой по теории вычислимости. [21]
Метод поиска пар чисел путем представления пары единственным числом г, кодирующим пару ( z) lf ( z) 2 ( использованный в доказательстве следствия 1.4), часто применяется в теории вычислимости. Ниже мы даем упражнение, в котором используется этот метод ( упр. [22]
Все эти различные исследования ведут к убедительному ( впрочем, неудивительному) подтверждению того, что логика хорновских дизъюнктов является универсальным вычислительным формализмом: по вычислительной силе она эквивалентна всем другим универсальным ( и взаимно эквивалентным) формализмам, традиционно изучаемым в теории вычислимости. [23]
В § 1 дается обзор неразрешимых проблем, возникающих в самой теории вычислимости, и обсуждаются некоторые методы доказательства неразрешимости. [24]
Поскольку на практике требование конечности числа состояний не является существенным, теории вычислимости с помощью машин Тьюринга и других вычислительных устройств, не ограниченных физическими габаритами, могут оказаться более перспективными, при условии, если будут известны быстродействие и объем памяти таких устройств. Идея о применимости интерпретирующей машины для моделирования поведения другой машины, как это имеет место для универсальных машин Тьюринга, лежит сейчас в основе обычных методов программирования. К этой идее непосредственно примыкают работы по перечислению методов решений, а также проблемы, связанные с описанием разрешимых задач принятия решения. Известные нам результаты относительно неразрешимости некоторых задач оказались весьма ценными, так как здесь наша интуиция обычно беспомощна. Но для нас более ценными могут оказаться теории эффективности алгоритмов, основанные, быть может, на соотношении между необходимым временем и объемом памяти, с одной стороны, и числом аргументов вычисляемой функции - с другой. Эти теории, несомненно, заменят машины Тьюринга, используемые сейчас для практического анализа разрешимости. [25]
Я вспоминаю, как спрашивал себя тогда может ли понятие сводимости, которое занимает столь важное место в теории вычислимости, играть роль в теории сложности, но я не видел, как осуществить эту связь. [26]
В этом месте нужно сделать два замечания. Во-первых, мы предполагаем, что наши функции кодируются на машинах Тьюринга в двоичной системе счисления, а не в унарной, которая обычно используется в теории вычислимости. Второе замечание заключается в том, что мы требуем только, чтобы а / была ограничена функцией из F, но не требуем, чтобы сама af принадлежала F. Это не только упрощает наши последующие доказательства2), но также оказывается ближе к реальной вычислительной практике. На практике получают верхнюю границу для объема памяти, необходимой при вычислении, причем эта граница не обязательно достигается. [27]
Как отмечалось в 2.2.7 ( а), эта группа есть свободное произведение двух свободных групп с объединенными бесконечными циклическими подгруппами, и, очевидно, условия предложения 2.2.9 выполнены. То же самое относится и к любому свободному произведению двух свободных групп с объединенными конечно порожденными подгруппами, поскольку в силу следствия 2.1.12 проблема вхождения для конечно порожденных подгрупп свободной группы разрешима, а из общих принципов теории вычислимости следует, что любой изоморфизм конечно порожденных групп всегда эффективно вычислим. [28]
Предложения, являющиеся отрицаниями, фактами или импликациями, образуют подкласс класса всех дизъюнктов и называются хорновскими дизъюнктами. Язык логического программирования называют иногда логикой хорновских дизъюнктов. Хорновские дизъюнкты пригодны фактически для любых целей, связанных с решением задач. Достаточность этого подкласса с точки зрения теории вычислимости обсуждается в гл. [29]
Знаменитая теорема Геделя о неполноте [1931] предстг ляет собой один из многих результатов о формальной арифи тике, в котором теория вычислимости и логика тесно nepenj таются друг с другом. Полные доказательства этих утверж ний выходят за рамки настоящей книги. Особое внимание мы уделим TJ роли, которую играет теория вычислимости, причем во мног случаях это связано с результатами, касающимися свойс продуктивных и креативных множеств. [30]