Машины Тьюринга - раздел Информатика, ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Машина Тьюринга – Это Система, Работающая В Дискретные...
Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины. Ячейка, в которой записан символ , называется пустой. Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где – состояние первой (слева) ячейки, – состояние второй ячейки и т.д.
Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние из конечного множества внутренних состояний , . Состояние называется заключительным и означает завершение работы машины. Состояние называется начальным и означает начало работы машины.
Программа Π, т.е. совокупность выражений (где ), называемых командами, каждое из которых имеет один из следующих видов:
сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку влево с заменой состояния на ;
сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку вправо с заменой состояния на ;
замена буквы в текущей ячейке на букву , а также замена состояния головки на состояние
Замечание 1.1) Команды не могут начинаться со слов .
2) .
Таким образом, машина Тьюринга – это пятерка .
Машинным словом называется слово , где – состояние ленты, – состояние головки, находящейся напротив ячейки с состоянием , занимающей то же положение среди других ячеек, что и буква в слове .
Пустое слово обозначим через .
Опишем преобразование машинного слова в машинное слово за один шаг работы машины :
если , то при и при ;
если , то при и при ;
если , то .
Машинное словополучается из машинного словас помощью машины Тьринга , если существует последовательность преобразований , , для которой , .
Пусть – множество натуральных чисел с нулем, .
Отображение , где , называется n–местной частичной функцией. Если , то частичная функция называется всюду определенной. Если , то частичная функция называется нигде не определенной.
Для любого числа через обозначим слово, состоящее из числа единиц: . Для любой –ки слово называется записью этой –ки.
Частичная функция , где , называется вычислимой по Тьюрингу, если существует машина Тьюринга такая, что
1) ;
2) машина применима к записnи n-ки ;
3) для и .
Пример 1.Построим машину Тьюринга , вычисляющую функцию . Пусть , где , , программа Π состоит из команд:
Логика это наука о законах мышления Это одна из древнейших наук Основные законы логики были сформулированы еще древнегреческим мыслителем... Современная математическая логика определяется как раздел математики... Данное учебно практическое пособие соответствует учебной программе курса Математическая логика и теория алгоритмов...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Машины Тьюринга
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ.
Формулы алгебры высказываний
Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.
В качестве примеров выс
Эквивалентные формулы алгебры высказываний
Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ и ψ АВ называются
Определение формального исчисления
Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия.
1. Имеется некоторое множество
Система аксиом и правил вывода
Используя понятие формального исчисления, определим исчисление высказываний (ИВ).
Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются про
Высказываний
Теорема 3.Пусть φ, ψ, χ ‑ формулы ИВ. Тогда имеют место следующие эквивалентности:
1) φ∧ φ≡φ, φ∨
Высказываний
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тож
Алгебраические системы
Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь гео
Формулы логики предикатов
Большинство определений этого параграфа будут индуктивными.
Введем понятие атомарной формулы сигнатуры Σ:
1) если t1, t2, T(Σ), то
В алгебраической системе
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической с
Пренексная нормальная форма в логике предикатов
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной форм
Система аксиом и правил вывода
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ).
Формулами ИПΣ
Предикатов
Утверждение 2.В ИПΣ выполнимы все эквивалентности ИВ из теоремы 3.
Утверждение 3. Пусть φ
Исчисления предикатов
Теорема 4. Все доказуемые в ИПΣ формулы являются тождественно истинными.
Доказательство проводим индукцией по длине вывода формулы. Очевид
Примитивно рекурсивные функции
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора.
Оператор суперпозиции (подстановки) ставит в соот
Частично рекурсивные функции
Оператор минимизации ставит в соответствие n+1-местной частичной функции n-местную частичную функцию так, что
и
или определены и не равны 0,
Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2.
1. ;
2. ;
3. ;
4. ;
5. ;
6.
Исчисление высказываний
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез.
1. ;
2. ;
3. ;
4. ;
Алгебраические системы.
Построить подсистему алгебраической системы , порожденную множеством (через обозначен булеан множества B, т.е. множество всех подмножеств множества B):
1.
2.
Формулы логики предикатов
Выписать все подформулы данной формулы сигнатуры
и определить свободные и связанные переменные формулы:
1.
2.
3.
4.
5.
В алгебраической системе
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда
1. х=1;
2. х=2n для некоторого натурального
Новости и инфо для студентов