Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

В начале работы с МТ устанавливается в состояние , на её ленту записывается исходное слово и считывающая головка помещается против 1-й (самой левой) ячейки (т.е. обозревает 1-ю букву слова ).

Если , то вся информация о начале работы запишется машинным словом

.

Теперь, как и при описании работы НА, сопоставим слову конечную или бесконечную последовательность машинных слов

(2)

Для этого находим в S команду вида

и в зависимости от значения , равного H, R или L, в качестве берём соответственно слово

Если , то в качестве искомой возьмём двухэлементную последовательность . В противном случае, как и выше, построим слово и т.д. Продолжая этот процесс, мы и получим искомую последовательность (2).

Последовательность слов в алфавите A, полученных удалением из слов символов-состояний, назовём путём переработки слова .

Если последовательность (2) конечна и оканчивается словом то говорят, что машина применима к слову и перерабатывает его в слово . Этот факт записывают в виде

.

Если же последовательность (2) бесконечна, то говорят, что машина не применима к слову .

Таким образом, любая МТ осуществляет частичное отображение множества слов в алфавите A в себя.

Приведем пример МТ, осуществляющей удвоение натуральных чисел. Как и при построении НА, натуральное число будем изображать в виде последовательности вертикальных чёрточек. В качестве внешнего алфавита возьмем множество , где 0 – пустой символ, а в качестве внутреннего –

.

Систему команд зададим таблицей:

Таблица 2.

Q A

0
|

В начале работы на ленту записывается слово , а вся информация о начале работы определится машинным словом

.

В качестве упражнения постройте последовательность машинных слов, начинающуюся словом .

Из сравнения определений НА и МТ видно, что в последний процесс преобразования слов разбит на более мелкие операции – них в каждый такт заменяется не более одной буквы слова. Кроме того, в них есть и другое сильное ограничение – расширение слова может происходить только за счёт приписывания новых символов слева или справа от слова (т.е. в начале его или конце). В связи с этим строить НА для решения задач, как правило проще, чем МТ. Так, задачу удвоения натурального числа можно решить НА со схемой

,

,

.

В нем всего лишь три команды вместо 9 в построенной выше машине, да и число тактов работы по удвоению слова существенно меньше. На первый взгляд может казаться, что и в принципе МТ имеют меньше возможностей по сравнению с НА. Однако А. Тьюрингом и Э. Постом была выдвинута гипотеза (или тезис) о том, что любой алгоритм над алфавитом A эквивалентен относительно A алгоритму, осуществляемому подходящей машиной Тьюринга (соответственно Поста).

Как и тезис Маркова А. А. Нормализации алгоритмов, эта гипотеза не может быть доказана, её можно лишь подкреплять какими-либо разумными доводами. Наиболее важным из них является известная к настоящему времени теорема о том, что всякий НА осуществим на МТ.

51. Определение частично рекурсивных функций. Основные функции.

52. Определение частично рекурсивных функций. Основные операции.

53. Определение частично рекурсивных функций.

54. Алгебраически неразрешимые проблемы.

55. Задачи Р- сложные. Полиномиально сложные задачи.

56. NP-проблемы. Экспоненциально сложные задачи.

57. Связь NP-проблем с Р-проблемами.

МНОГОЗНАЧНЫЕ ФУНКЦИИ

Наряду с булевыми функциями в приложениях используются -значные функции и при > 2. Будем считать, что аргументы таких функций и сами они принимают значения из множества чисел

Определение 1. Функцией -значной логики, или -значной функцией, от n переменных при n 1 называется произвольное отображение

-значными функциями от 0 переменных называются функции-константы 0,1,..., -1.

Множества всех -значных функций и всех -значных функций от n переменных обозначим соответственно через и .

При изучении -значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, сходным образом определяются равенство функций, существенные и несущественные переменные, функции от n переменных, тождественно равные константам 0, 1, ..., -1, подфункции и т. д.

Так как множество конечно, то -значную функцию от n переменных можно задать таблицей ее значений на всех наборах (или векторах) из . При этом условимся записывать их в порядке возрастания как чисел в А-ичной системе счисления. Непосредственно из табличного задания видно, что число различных -значных функций от n переменных равно . При >2 табличное задание -значных функций практически еще более трудно осуществимо, чем задание булевых функций. В связи с этим важным является вопрос о разработке аналитических способов задания -значных функций. При этом, как и в случае =2, естественно было бы воспользоваться какими-либо простейшими функциями и, в .частности, бинарными операциями на множестве .

Множество можно рассматривать как кольцо вычетов по

модулю , и потому можно считать определенными на операции сложения и умножения по модулю . Будем эти операции при >2 обозначать теми же значками • , + , что и операции над числами. Используя эти операции и функции-константы, можно построить кольцо многочленов от переменных . Каждый многочлен этого кольца представляет -значную функцию от n переменных. Ниже будет доказано, что при простом , когда есть поле, многочленами представляются все -значные функции. При составном это не так. Действительно, если — собственный делитель числа , то все функции , представляемые многочленами, сохраняют отношение сравнимости по модулю :

.

Ясно, что не все -значные функции обладают этим свойством. Используя операции сложения и умножения, а также элементарные функции

можно получить представление -значной функции, сходное с совершенной дизъюнктивной нормальной формой для случая =2.

(1)

Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания:

,

.

Для -значных функций, как и в двоичном случае, можно ввести понятия суперпозиции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной систем функций и т. д. Приведем примеры полных систем -значных функций.

1. Из представления (1) следует, что полной является система функций

.

1. Так как в разложении (1) операцию сложения можно заменить на дизъюнкцию (выбор максимума), то полной является также система функций

.

3. Наряду с разложением (1) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции

где

Отсюда следует, что полной является система функций

.

ФУНКЦИИ ШЕННОНА И ИХ ОЦЕНКИ.

Для описания сложности контактных схем К. Шенноном в работе [ 12 ] была введена числовая функция (n), равная такому наименьшему числу, что контактными схемами сложности не более (n) можно реализовать любую булеву функцию от n переменных:

(n)= (f),

или более подробнее,

где минимум берется по всем контактным схемам S, реализующим функцию f.

Аналогичные функции можно ввести и для других типов схем, реализующих булевы функции, при различных определениях сложности схем. Все такие функции называют функциями Шеннона. Примерами функций Шеннона являются функции

для -схем и функции

=

для функциональных схем в любом фиксированном базисе.

В отмеченной выше работе [ 12 ] был указан подход к нахождению нижних оценок функций Шеннона и найдена нижняя оценка для (n) .точнее, была доказана

Теорема 1.Для любого >0 и больших n выполняется неравенство

Причем доля функций , для которых

Характеристики

Список файлов ответов (шпаргалок)