- •2. Сочетания, размещения, перестановки, булеаны.
- •3. Понятие атрибута, кортежа и схемы отношения. Представление атрибутов, кортежей и схем отношений на языке семантических сетей.
- •5. Бинарные отношения, свойства бинарных отношений и их представление на языке семантических сетей.
- •6. Соответствия и их типология. Представление соответствий на языке семантических сетей.
- •11. Отношение гомоморфизма на алгебраических системах. Представление отношения гомоморфизма на языке семантических сетей.
- •12. Отношение изоморфизма и автоморфизм алгебраических систем. Представление отношения изоморфизма и автоморфизма на языке семантических сетей.
- •13. Понятие реляционной структуры. Типология элементов реляционной структуры. Представление реляционных структур на языке семантических сетей.
- •15. Понятие формального языка. Типология формальных языков. Графовые формальные языки.
- •16. Алфавит и синтаксис формального фактографического языка семантических сетей.
- •17 .Понятие логического формального языка. Примеры логических формальных языков
- •18 Логические операции. Понятие высказывания. Типология высказываний.
- •20 Понятие совершенной конъюнктивной нормальной формы и совершенной дизъюнктивной нормальной формы. Способы построения.
- •24. Язык исчисления предикатов.
- •26. Алфавит, синтаксис и ключевые узлы графового логического языка.
- •27. Понятие формальной модели обработки информации. Понятие абстрактной машины. Машина Тьюринга.
- •28. Абстрактные машины логического вывода.
- •29. Типология и представление целей в машинах логического вывода.
- •30.Средства описания динамических предметных областей.
27. Понятие формальной модели обработки информации. Понятие абстрактной машины. Машина Тьюринга.
Машина Тьюринга состоит из:
1) управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество ;
2) ленты, разбитой на ячейки, в каждой из которых может быть записан один из символов конечного алфавита;
3) устройства обращения к ленте, т. е. считывающей и пишущей головки, которая в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (быть может, совпадающий с прежним или пустой, т. е. стирает символ), сдвигается на ячейку влево или вправо или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом). Среди состояний управляющего устройства выделены начальное состояниеи заключительное состояние, которое будемобозначать (z здесь понимается не как числовая переменная, а как мнемонический знак конца). В начальном состоянии машина находится перед началом работы; попав в заключительное состояние, машина останавливается. Таким образом, память машины Тьюринга — это конечное множество состояний (внутренняя память) и лента (внешняя память). Лента бесконечна в обе стороны, однако в начальный момент времени только конечное число ячеек ленты заполнено непустыми символами, остальные ячейки пусты, т. е. содержат пустой символ (пробел), Из характера работы машины следует, что и в любой последующий момент времени лишь конечный отрезок ленты будет заполнен символами. Поэтому важна не фактическая (как говорят в математике, актуальная) бесконечность ленты, а ее неограниченность, т. е. возможность писать на ней сколь угодно длинные, но конечные слова. Данные машины Тьюринга — это слова в алфавите ленты; на ленте записываются и исходные данные, и окончательные результаты. Элементарные шаги машины — это считывание и запись символов, сдвиг головки на ячейку влево и вправо, а также переход управляющего устройства в следующее состояние. Детерминированность машины, т. е. последовательность ее шагов, определяется следующим образом: для любого внутреннего состоянияи символаоднозначно заданы: а) следующее состояние; б) символ , который нужно записать вместов ту же ячейку (стирание символа будем понимать как запись пустого символа ); в) направление сдвига головки, обозначаемое одним из трех символов: L (влево), R (вправо), Е (на месте). Это задание может описываться либо системой правил (команд), имеющих вид
либо таблицей, строкам которой соответствуют состояния, столбцам — входные символы, а на пересечении строкии столбца записана тройка символов, и, наконец,блок-схемой, которую будем называть диаграммой периодов.
Недетерминированная машина Тьюринга моделирует алгоритмы с некоторой «свободой выбора», причем нас интересует, сколько времени понадобится, если с выбором «всегда будет везти». По крайней мере некоторые команды недетерминированной машины Тьюринга NT при одной и той же истории ее работы и, значит, при одном и том же ее полном состоянии могут выполняться разными способами. Для каждого внутреннего состояния машины и читаемого с ленты символа эти способы заданы.
У машины Тьюринга NT также имеется конечный набор внутренних состояний , и алфавит символов на ленте , тоже конечен. Однако правила
действии имеют вид списков:
гдеl — это максимальное число вариантов выполнения действия. Если для некоторых внутренних состояний и читаемых символов symj вариантов меньше, то последний будем дублировать так, чтобы их стало l.
Перед выполнением очередного действия из одной машины возникает l машин. Записи на их лентах одинаковы — такие, какие были у их «предка», но с этого момента их пути расходятся: каждая машина выполняет свой вариант действия из списка. Процесс работы детерминированной машины Тьюринга Т (и любой рассмотренной раньше машины) может быть изображен в виде линейной последовательности действий, а процесс работы недетерминированной машины NT — в виде дерева, вершинами которого являются выполняемые действия, а ребрами — переходы от одного действия к следующим (рис. 9.2). Таким образом, она одновременно решает задачу разными способами, чтобы не упустить тот, при котором «везет». Каждый способ — это последовательность машинных операций, которой соответствует цепь дерева работы машины NT с началом в корне.
Если по некоторой цепи действия заканчиваются, то возможны два исхода: задача решена или решение не найдено. В первом случае все остальные машины, размножившиеся к этому моменту, тоже кончают работу и превращаются в одну машину. Во втором — они продолжают работать. Если же по всем цепям произойдет окончание вычислений с отрицательными результатами, то все машины тоже сливаются в одну: задача не имеет решения. Других обменов информацией между различными вариантами процесса работы машины не происходит.