Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов




Скачать 26.75 Kb.
НазваниеКосовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов
Дата конвертации19.04.2013
Размер26.75 Kb.
ТипДокументы
Косовский Н.К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей Междунар. научно-техн. конф.– Пенза: ПДЗ, 2010. – С. 5-7.

ЭКВИВАЛЕНТНОСТЬ УСЛОВИЙ
ЭФФЕКТИВНОСТИ МАШИН ТЬЮРИНГА,
НОРМАЛЬНЫХ И ПРОДУКЦИОННЫХ АЛГОРИТМОВ


Н.К. Косовский

Санкт-Петербургский государственный университет,
г. Санкт-Петербург, Россия

Предлагается формализация понятия продукционного алгоритма. Доказано, что расширенные тезисы Тьюринга для рассматриваемых понятий алгоритмов эквивалентны.


Kosovsky N.K. Turing machine, normal and rule-oriented algorithms effectiveness conditions equivalence. A formalization of a rule-oriented algorithm notion is proposed. It is proved that the extended Turing theses for considered notions of algorithm are equivalent.

Для решения многих задач искусственного интеллекта большое значение имеет эффективность этого решения, изучением которой занимается алгоритмическая теория сложности.

Тезис Чёрча занимает исключительное положение в математике. Он не может быть ни доказан, ни опровергнут.

В 2000 году опубликована формулировка расширенного тезиса Чёрча-Тьюринга для машины Тьюринга в форме: «Интуитивно эффективно вычислимые алгоритмы совпадают с алгоритмами, вычислимыми за полиномиальное число шагов на машинах Тьюринга» [1].

На основе результатов, полученных в [2], легко доказать эквивалентность этой формулировки тезиса другой, в которой машины Тьюринга заменены алгоритмами Маркова. Доказательство основывается на двух леммах о полиномиальности проверки возможности выполнения хотя бы одного правила (замены) и о полиномиальности выполнения каждого шага алгоритма.

Буквальная замена нормальных алгоритмов RAM-программами с умножением приводит к неэквивалентной формулировке расширенного тезиса Чёрча-Тьюринга как по функциям, так и по предикатам (последнее, если P NP) [2].

Однако расширенный тезис Чёрча-Тьюринга из [1] эквивалентен в своей буквальной формулировке для вводимого здесь понятия продукционного алгоритма без размножения переменных (для слов) в итеративных (не заключительных) правилах.

Каждое правило продукционного алгоритма представляет собой однопосылочное правило Поста, в котором каждая переменная для слов, встречающаяся в заключении, находится и в посылке. Для итеративных правил вводится дополнительное ограничение: для каждой переменной число различных вхождений её в заключение правила не превосходит числа различных вхождений её в посылку правила.

Каждое правило сопровождается полиномиально быстрым (принадлежащим классу P [3]) алгоритмом, разрешающим его применение.

Конечная совокупность правил используется как правила в нормальном алгоритме.

Продукционный алгоритм заканчивает работу, если не применимо ни одно из его правил или было выполнено заключительное правило.

Каждое применение правила считается за шаг выполнения алгоритма.

Теорема. Формулировки расширенного тезиса Чёрча-Тьюринга для машин Тьюринга и для продукционных алгоритмов эквивалентны.

Доказательство может быть получено на основе результатов из [2].

Отметим, что отмена ограничения на число различных вхождений одной и той же переменной в заключение правила приводит, так же, как в [4], к неэквивалентной буквальной формулировке расширенного тезиса Чёрча-Тьюринга для такой модификации понятия продукционного алгоритма.

Библиографический список

1. Du D.Z., Ko K.I. Theory of Computational Complexity // A Wiley-Interscience Publication. John Wiley & Sons, Inc. 2000. – 491p.

2. Косовский Н.К. Условия полиномиальности алгоритмов, реализуемых на машинах Тьюринга с оракулами-функциями // XVII Международная школа-семинар «Синтез и сложность управляющих систем» им. академика О.Б. Лупанова (Новосибирск, 27 октября – 1 ноября 2008 г.). – Новосибирск: Изд-во Института математики, 2008. – C. 70 – 74.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

4. Косовский Н.К., Косовская Т.М. Полиномиальность и NP-трудность задачи вычисления знака постоянного терма // Математические вопросы кибернетики. – Вып.16. – М.: Физматлит, 2007. – С. 125 – 128.

Добавить в свой блог или на сайт

Похожие:

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconПрограмма дисциплины «Организация, управление и администрирование в социальной работе»
Такая деятельность необходима для повышения эффективности функционирования системы социальной защиты населения, и, как следствие,...

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconСистема кондиционирования воздуха (скв) служит для обеспечения нормальных жизненных условий для экипажа и пассажиров,которые определяются основными
Скв) служит для обеспечения нормальных жизненных условий для экипажа и пассажиров,которые определяются основными физиолого-гигиеническими...

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconРешение проблемы безопасности жизнедеятельности состоит в обеспечении нормальных (комфортных) условий производственной деятельности людей, в защите человека и окружающей его производственной среды от воздействия вредных факторов,
Улучшение условий и повышение безопасности труда на производстве являются важнейшей социально-экономической задачей развития предприятия...

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconКритерии эффективности алгоритмов обнаружения манёвров динамических объектов
Описана методика применения разработанных критериев при решении задач сравнительного анализа и оптимизации алгоритмов обнаружения...

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconТехническое задание для участия в открытом конкурсе по лоту №1 «Газоснабжение с. Уват Уватского района»
Предусмотреть мероприятия по обеспечению нормальных условий труда согласно действующему законодательству

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconКомплекс программ для оценки эффективности алгоритмов решения нелинейных навигационных задач фильтрации
Разработка такого комплекса позволит существенно облегчить процесс синтеза и анализа точности при проектировании алгоритмов решения...

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconИсследование эффективности локально-адаптивных алгоритмов нелинейной фильтрации для обработки электрокардиограмм

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconКонтрольная работа по дисциплине: «Безопасности жизнедеятельности» на тему: «Показатели эффективности»
Показатели эффективности мероприятий по улучшению условий труда

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconПромыслово-биологическая характеристика и перспективы оптимизации использования продукционных свойств популяции леща ( abramis brama (L.)) Вислинского залива балтийского моря
Оптимизации использования продукционных свойств популяции леща (abramis brama (L.)) Вислинского залива балтийского моря

Косовский Н. К. Эквивалентность условий эффективности машин тьюринга, нормальных и продукционных алгоритмов iconКонкурс капитанов!
В квне все происходит не так, как у нормальных людей. Хотя у нормальных людей есть свои разумные традиции. Например, учебники каждый...


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница