Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Разветвление машин Тьюринга




Пусть машины Т1, Т2, Т3 заданы программами П1, П2, П3 и внутренние алфавиты машин не пересекаются. Пусть q1i и q1j - какие-либо различные заключительные состояния машины Т1. Заменим в программе П1 состояние q1i некоторым начальным состоянием q21 машины Т2, а состояние q1j-некоторым начальным состоянием q31 машины Т3. Объединив новую программу с П2 и П3, получим программу П, задающую машину . Говорят, что Т есть разветвление машин Т1 и Т2, работающих под управлением Т1.

Эквивалентность машин Тьюринга

Машины Тьюринга Т1 и Т2 называются эквивалентными в алфавите А, если для всякого входного слова Р в алфавите А выполняется соотношение: Т1(Р)=Т2(Р), которое означает, что Т1(Р) и Т2(Р) определены или не определены одновременно, т.е. применимы или не применимы к слову Р. Эквивалентность машин Т1 и Т2 обозначается .

Символ называется знаком условного равенства.

Понятие об алгоритмической неразрешимости

Словосочетание «решить задачу» допускает множество толкований. В математике иногда решают задачу с помощью интуиции (озарения). Рассмотрим решение с алгоритмической точки зрения: задача может быть решена, если существует алгоритм, приводящий к результату (решению задачи). Если для решения некоторой задачи построен решающий ее алгоритм, говорят, что задача алгоритмически разрешима. Во многих случаях алгоритм может быть найден. Но что означает ситуация, когда не удалось найти необходимый алгоритм? Ставить и разрешать математически точно вопросы об алгоритмической неразрешимости задач стало возможно только после появления формального определения понятия алгоритма. К настоящему времени выявлено достаточно много задач, для которых доказано, что не существует алгоритма, их решающего. Такие задачи называются алгоритмически неразрешимыми.

 


Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...