Машины Тьюринга - раздел Философия, Глава 1. Основы теории множеств
...
Рассмотрим еще один способ определения вычислимых функций, следуя в изложении [29, стр. 12-14]. Формулировка, выраженная в терминах воображаемой вычислительной машины, была дана английским математиком Аланом Тьюрингом в 1936 г. [4]. Главная трудность при нахождении этого определения была в том, что Тьюринг искал его до создания реальных цифровых вычислительных машин. Познание шло от абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг позднее сыграл вдохновляющую роль в развитии вычислительных машин.
На неформальном уровне мы можем описывать машину Тьюринга как некий черный ящик с лентой. Лента разбита на ячейки и каждая ячейка может содержать пустой символ 0, либо непустой символ 1. Лента потенциально бесконечна в обе стороны в том смысле, что мы никогда не придем к ее концу, но в любое время лишь конечное число ячеек может быть непустым. В начале лента содержит числа входа, в конце - число-выход. В промежуточное время лента используется как пространство памяти для вычисления.
Если мы откроем черный ящик, то обнаружим, что он устроен очень просто. В любой момент времени он может обозревать лишь одну ячейку памяти. Устройство содержит конечный список инструкций (или состояний) q0, q1,..., qn. Каждая инструкция может указать два возможных направлений действий; одного нужно придерживаться, если на обозреваемой ячейки ленты находится 0, а другого, - если там находится 1. В любом случае следующее действие может состоять из таких трех типов элементарных шагов:
1) символ (возможно, такой же, как старый) пишется на обозреваемой ячейки ленты, при этом предыдущий символ стирается;
2) лента сдвигается на одну ячейку влево или вправо;
3) указывается следующая инструкция.
Таким образом, список инструкций определяет некоторую функцию перехода, которая по данной инструкции и обозреваемому символу указывает три компоненты того, что нужно делать. Мы можем формализовать эти идеи, взяв в качестве машины Тьюринга эту функцию перехода.
Определение. Машина Тьюринга - это функция M такая, что для некоторого натурального числа n, область определения этой функции есть подмножество множества {0, 1,..., n}´{0, 1}, а область значений есть подмножество множества {0, 1}´{Л, П}´{0, 1, ..., n}.
Например, пусть M(3,1) = <0, Л, 2>. Подразумеваемый смысл этого состоит в том, что как только машина дойдет до инструкции q3, а на обозреваемой ячейки написан символ 1, она должна стереть 1 (оставляя на ячейке 0), передвинуть ленту так, чтобы обозреваемая ячейка стала левая соседняя ячейка от той, которая обозревалась, и перейти к следующей инструкции q2. Если M(3,1) не определено, то как только машина дойдет до инструкции q3, а на обозреваемой ячейки написан символ 1, то машина останавливается. (Это единственный путь остановки вычисления.)
Такая подразумеваемая интерпретация не включена в формальное определение машины Тьюринга, но она мотивирует и подсказывает формулировки всех следующих определений. В частности, можно определить, что означает для машины M передвижение (за один шаг) от одной конфигурации до другой. Нам не нужно здесь давать формальных определений, так как они являются простыми переводами наших неформальных идей.
Входные и выходные данные - это строчки из 1, разделенные 0. Пусть <n> будет строчкой из 1 длины n+1. Тогда
<n1> 0 <n2> 0 ... 0 <nk>
получено комбинацией k строчек из 1, каждая отделена от другой 0.
Наконец, мы можем определить вычислимость.
Определение. Пусть Df Í Nk - область определения k-местной функции f: Df ® N (N - множество натуральных чисел). Функция f называется вычислимой, если существует машина Тьюринга M такая, что как только M начинает с инструкции q0, обозревая самой левый символ строки
<n1> 0 <n2> 0 ... 0 <nk>,
(вся остальная часть ленты пуста), тогда:
· если f(n1, n2,..., nk) определено, то M в конце концов остановится, обозревая самый левый символ строки <f(n1, n2,..., nk)>, при этом часть, находящаяся справа от этой строчки, пустая;
· если f(n1, n2,..., nk) не определено, то M никогда не останавливается.
Заметим, что имеется бесконечное множество машин Тьюринга, для каждой вычислимой функции своя. Более того, для любой вычислимой функции имеется бесконечное множество машин Тьюринга, вычисляющих эту функцию.
Пример 6.3. Построим машину Тьюринга, вычисляющую сумму n1+n2.
Зададим функцию M следующим образом:
M(0, 1) = <1, П, 0>;
M(0, 0) = <1, П, 1>;
M(1, 1) = <1, П, 1>;
M(1, 0) = <0, Л, 2>;
M(2, 1) = <0, Л, 3>;
M(3, 1) = <0, Л, 4>;
M(4, 1) = <1, Л, 4>;
M(4, 0) = <0, П, 5>.
Посмотрим как происходит сложение 1+1. В текущей строке символов обозреваемый символ выделен.
Номер
инструкции
Текущая строка
символов
Комментарий
0110110
прохождение через первое слагаемое
0110110
0110110
заполнение промежутка
0111110
прохождение через второе слагаемое
0111110
0111110
конец второго слагаемого
0111110
стирание 1
0111100
стирание второй 1
0111000
движение назад
0111000
0111000
0111000
остановка
0111000
Мы должны заметить, что многие детали нашего определения машины Тьюринга до некоторой степени произвольны. Если бы было более одной ленты, то класс вычислимых функций остался бы неименным, хотя некоторые функции могли бы быть вычислены более быстро. Аналогично, мы могли бы допускать больше символов, чем 0 и 1, или же у нас могла бы быть лента бесконечная только в одну сторону от начальной точки вместо имеющихся бесконечной в обоих направлениях. Ни одно из этих изменений не затрагивает класса вычислимых функций. Что действительно существенно в этом определении - это разрешение произвольно большого количества материала для запоминающего устройства и произвольно длинных вычислений.
Дорогой читатель перед Вами книжка которую мы довольно долго писали... Данное пособие предназначено для студентов технических специальностей у которых на курс математической логики...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Машины Тьюринга
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Начальные понятия теории множеств
Понятие множества является основным, неопределяемым понятием, поэтому мы можем его только пояснить, например, с помощью следующего псевдоопределения.
Определение:
Интуитивный принцип объемности
Определение. Множества Aи B считаются равными, если они состоят из одних и тех же элементов.
Записывают A=B, если A и B равны, и A
Отношения
Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары <
Функции
Определим понятие "функция", следуя Дирихле. По сути дела при таком определении мы отождествляем функци
Эквивалентность
Одним из самых важных типов отношений является отношение эквивалентности на множестве.
Определение. Рефлексивное, симметричное и транзитивное отношение r н
Зачем мы изучаем математическую логику?
Логика есть наука о законах и формах познающего мышления. Логика изучает мышление, но не всякое мышление, а лишь те мыслительные процессы, которые направлены на обнаружение и обосно
Высказывания
Мы начинаем изучать математическую логику со сравнительно ограниченного и нетрудного ее раздела, чтобы затем иметь возможность продвигаться вширь и вглубь. Этот раздел посвящен изуч
Логические связки
Грамматическими средствами в разговорном языке из нескольких высказываний можно составить сложное (составное) высказывание. Например, с помощью союзов "и", "или"
Формулы логики высказываний
Мы определим формальный язык для описания логики высказываний. Это описание чисто синтаксическое и оно не требует, чтобы формулы логики высказывания имели какую-то семантику (смысл)
Равносильность формул
Пусть A и B - две формулы и {X1, X2,…, Xn} - множество всех выск
Определение.
· Формула называется выполнимой, если на некотором наборе распределения истинностных значений переменных она принимает значение И.
· Формула называется тождественно-ложной ил
Нормальные формы формул
Содержание этого параграфа изложим, следуя [24].
Будем рассматривать формулы, содержащие только логические операции &, Ú, Ø. Символы & и Ú назы
Разрешимость для логики высказываний
Проблемой разрешимости для логики высказываний называют следующую проблему: существует ли алгоритм, который позволил бы для произвольной формулы в конечное число шагов определить, я
Модель исчисления высказываний
Пусть B - множество высказываний с обычными логическими операциями конъюнкции, дизъюнкции и отрицания и равенство высказываний интерпретируется как их равносильность.
Во второй главе показ
Определение.
Если булева алгебра M - двухэлементна (т. е. содержит только Ë и Î), то булевы функции называются двоичными функциями.
Если в двухэлементной булевой алгебре элементы &Eum
Полные системы булевых функций
Определение.Система функций {f1, f2,…, fn} называется полной, если любая булева функция может быть выражена через функции f
Переключательные элементы
Пусть имеется "черный ящик" - некоторое устройство, внутренняя структура которого нас не интересует, а известно лишь, что оно имеет n упорядоченных "входов" (например, занумеров
Формулы логики предикатов
Существуют такие виды логических рассуждений, которые нельзя формализовать на языке логики высказываний. Вот примеры таких рассуждений:
1. Каждый любит сам себя. Значит, ко
Интерпретации
Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов.
Определение. Под интерпретацией мы будем понимат
Выполнимость и общезначимость
Определение.Формула A выполнима в данной интерпретации, если существует такой набор <a1, a2,…, an>, aiÎM, значений св
Формальные аксиоматические теории
Формальная теория представляет собой множество чисто абстрактных объектов (не связанных с внешним миром), в которой представлены
Исчисление высказываний
Оказывается множество тавтологий логики высказываний можно описать в рамках простой формальной аксиоматической теории - исчисления высказываний.
Определим исчисление высказ
Теорема 5.2
1. Любая аксиома в исчислении высказываний является тавтологией.
2. Любая теорема в исчислении высказываний является тавтологией.
Доказательство. То, что каждая аксиома A1-A3 явля
Исчисление предикатов
Исчисление предикатов - это аксиоматическая теория, символами которой являются, по существу, те же символы, что и в логике предикатов:
1) символы предметных переменных: x
Теорема 5.4
1. Аксиомы исчисления предикатов - общезначимые формулы.
2. Формула, получающаяся из общезначимых формулы по любому из правил вывода 1-4, является общезначимой.
3. Любая доказуема
Логический вывод
Терпеть не могу логики. Она всегда банальна и нередко убедительна.
Оскар Уайльд
Формальная математика основывается на аксиоматическом методе. Внача
Метод резолюций
Логическое программирование является, пожалуй, наиболее впечатляющим примером применения идей и методов математической логики (точнее, одного из ее разделов - теории логического выв
Неполнота математики
Таким образом, показано, что класс всех теорем исчисления предикатов совпадает с классом общезначимых формул. На этом примере мы видим силу формального аксиоматического метода. Но н
Понятие алгоритма и неформальная вычислимость
В этом разделе будет уточнено понятие алгоритма. Кроме того, будут даны строгие математические понятия, которые формализуют представление о том, что некоторые функции поддаются вычи
Определения
Этот подход к формализации понятия алгоритма принадлежит Гёделю и Клини (1936).
Основная идея Гёделя сос
Ламбда - исчисление
Значение ламбда-исчисления
Ламбда-исчисление было изобретено Алонсом Чёрчем около 1930 г. Чёрч первоначально строил l-исчисление как часть
Тезис Чёрча
За последние 60 лет было предложено много различных математических уточнений интуитивного понятия алгоритма. Три из этих подхода мы разобрали. Перечислим некоторые другие альтернати
Сложность алгоритмов
Применение математики во многих приложениях, требует как правило, использования различных алгоритмов. Для решения многих задач не трудно придумать комбинаторные алгоритмы, сводящиес
NP-трудные и NP-полные задачи
Различные задачи, относящие к классу NP являются эквивалентными относительно некоторого отношения, которое мы сейчас определим.
Определение. Задача Q по
Трехзначная система Я. Лукасевича
Эта пропозиционная логика была построена Я. Лукасевичем в 1920 году [34]. Лукасевич обозначил «истину» за «1», «ложь» за «0» и ввел третье значение – «нейтрально» - ½. Основными функциями им
Логика Гейтинга
Из закона исключенного терьего в двузначной логике выводятся:
1. ØØх É х 2. х É ØØх
Гейтинг создал трехзначную пропозицио
Трехзначная система Бочвара Д.А.
Система создавалась Бочваром Д.А. [36] для разрешения парадоксов классической математической логики методом формального доказательства бессмысленности определенных высказываний. Нап
К - значная логика Поста Е.Л.
Логика Поста [37] является обобщением частного случая – двузначной логики, когда К=2. Действительно, по Посту значения истинности принимают значения 1, 2,…,К (при К ³ 2 и К – к
Цели и задачи дисициплины
Цели преподавания дисциплины является ознакомление студентов с основами математической логики, теории алгоритмов с методами оценки сложности алгоритмов и построения эффективных алгоритмов.
Наименование тем
Введение
История развития математической логики и теории алгоритмов. Математическая логика и основания математики. Теория алгоритмов и принципиальные возмож
КОНТРОЛЬНАЯ № 2
Вариант 1
1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:
"Для того, чтобы x бы
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Рассмотрим еще один способ определения вычислимых функций, следуя в изложении [29, стр. 12-14]. Формулировка, выраженная в терминах воображаемой вычислительной машины, была дана английским математиком Аланом Тьюрингом в 1936 г. [4]. Главная трудность при нахождении этого определения была в том, что Тьюринг искал его до создания реальных цифровых вычислительных машин. Познание шло от абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг позднее сыграл вдохновляющую роль в развитии вычислительных машин.
Новости и инфо для студентов