- •Математическая логика
- •Парадигмы формальной логики.
- •Предмет, цель, задачи и содержание читаемого курса лекций.
- •Место читаемого курса о законах и формах правильного мышления.
- •Концептуальный базис математической логики.
- •Построение математической логики.
- •Классическая логика высказываний.
- •Язык классической логики предикатов (я.Л.П.).
- •Примеры:
- •Алгебра логики предикатов.
- •Пояснения:
- •Квантификация предикатов.
- •Эквивалентные преобразования кванторных формул.
- •Классические логические исчисления.
- •Цель классических и.В. И и.П.
- •Метасимволика и.В. И и.П.
- •Построение логических исчислений.
- •Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- •Основные требования к алгоритмам.
- •Основная терминология теории алгоритмов.
- •Основные теоремы теории алгоритмов.
- •Параметры алгоритма.
- •Основная гипотеза теории алгоритмов.
- •Алгоритмические (формальные математические) модели.
- •Блок-схемы алгоритмов.
- •Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- •1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- •Формальное определение машины Тьюринга.
- •Основной тезис Тьюринга.
- •Нормальные алгорифмы (алгоритмы).
- •Рекурсивные функции.
- •Примитивно-рекурсивные функции.
- •Оператор минимизации (- орератор).
- •Основной тезис Черча.
- •Алгоритмически неразрешимые проблемы.
1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
Имеем следующую интерпретацию смены ситуаций:
a0 |
a2 |
a1 |
a0 |
a0 |
a0 |
a4 |
a1 |
a0 |
a0 |
a0 |
a4 |
a2 |
a0 |
a0 |
2) Машина Т=<a0, a, q0, qz, q0 a0 q0 a dп, q0 a q0 a dп> будет работать бесконечно, заполняя все ячейки ленты символами а вправо от начальной пустой ячейки (исходная информация на ленте - пустые символы а0 в каждой ячейке ленты).
Примечания:
Соответствие, устанавливаемое машиной Тьюринга между теми исходными данными, к которым она применима ( то есть если она приводит к результату) и результатами ее работы представляет собой некоторую словарную функцию (в математическом смысле) Т(*исх*резисхрезпром.
Если для функции имеется машина ее реализующая, то говорят, что эта функция вычислима по Тьюрингу. Функция, для вычисления которой существует алгоритм, называется вычислимой.
Поскольку слово (*, m) можно отождествить с натуральным числом (в m-ичной системе счисления), то уточнение понятия вычислимой словарной функции приводит и к уточнению понятия вычислимой числовой функции f:NkN, kN. Тьюринг доказал. что класс числовых функций, вычислимых на машине Тьюринга, совпадает с классом частично-рекурсивных функций.
Формальное определение машины Тьюринга.
Машина Тьюринга Т=<A,Q,> полностью определяется:
внешним алфавитом А=а0, а1… аm;
Алфавитом внутренних состояний Q=q0, q1… qn;
Программой, то есть совокупностью выражений Т(i, j) (i=0,n; j=0,m), каждое из которых имеет вид следующей команды qj ai qk aL dt (k=0,n; L=0,m; dt dЛ, dп, dн.
Машина Тьюринга есть формальная детерминированная система F.S=<L,D>=<A,S;Ax,R>, порождающая множествоLсвоих конфигураций (машинных слов)1qjai2(1,2А*,1и2 могут быть пустыми). Единственная аксиома – начальная конфигурацияq0(А*), правила выводаR– система команд (программа)Т(i,j).
Примечания:
Очевидно, что всякий алгоритм является формальной системой F.S, что следует из тезиса Тьюринга: «Любой алгоритм может быть реализован машиной Тьюринга».
Поскольку машина Тьюринга есть алгоритм, то записью последнего является программа , а алгоритмом выполнения – описание устройства машины Тьюринга.
Пример:
Построить машину Тьюринга для вычисления базисной рекурсивной функции f(x)=x+1, xN0 Имеем T=<A=a0, Q=q0, qz, =
A\Q |
q0 |
qz |
a0 |
dн qz |
a0 dн qz |
|
dn q0 |
dн qz |
>
или
Пусть:
а) х=0, тогда q0 a0…a0 qzdн;
б) х=2, тогда q0 a0 q0 dn q0 a0 dn qz dн
Основной тезис Тьюринга.
Утверждение: «Для любой вычислимой функции можно построить машину Тьюринга, реализующую ее» - является гипотезой, называемой тезисом Тьюринга. (Часто этот тезис формулируют так: «Всякая вычислимая функция вычислима по Тьюрингу.)
Напомним, что этот тезис нельзя доказать, так как он объединяет два понятия – расплывчатое, интуитивное понятие вычислимой функции и строгое понятие машины Тьюринга.