Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Тема 8.3 Уточнения понятия алгоритм.






     

    Существует четыре уточнения понятия алгоритм (тезисы):

    1. Тезис Тьюринга: Общий метод (алгоритм) для решения задач из класса финитно-поставленных существует тогда и только тогда, когда кодовая функция , вычисляется на машине Тьюринга.

    2. Тезис Чорча: Функция f, определенная на множестве N вычислима тогда и только тогда, когда она является частично рекурсивной.

    3. Нормальный алгоритм Маркова:

    , где , все рi, ai – слова в алфавите А, А – конечный алфавит.

    Схема работает следующим образом: пусть - это слово из алфавита А, тогда отыскиваем сверху первую строку, левая часть которой входит по крайней мере 1 раз в слово :

    Заменяем самое левое вхождение рi в слове самым правым вхождением ai. Если ни одно рi не входит в слово , то будем считать, что алгоритм не применим к этому слову.

    Заменив рi на ai, получим новое слово и повторим процесс.

    Процесс заканчивается на том шаге, когда .

    4. Тезис Маркова: Для того, чтобы класс финитно-поставленных задач имел алгоритм решения необходимо и достаточно, чтобы существовал нормальный алгоритм Маркова, перерабатывающий код условия задачи в код ее ответа.

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.