Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Область использования машины Тьюринга

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость

Понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно известные нам вычислительные процедуры на элементарные операции: Тьюринг привел ряд доводов в пользу того, что повторения его элементарных операций было бы достаточно для проведения любого возможного вычисления. Поэтому машина Тьюринга (МТ) используется:

1) если требуется доказать возможность алгоритмической реализации вычислительной функции;

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

Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.

Для этого мы моделируем работу произвольного алгоритма в терминах рассматриваемой задачи. Затем определяется класс машин-вычислителей, которые могут решить данную задачу – формально описываются правила работы машины, исходные данные, ограничения и т.д. (поскольку в определении задачи ничего не говорится о программах так таковых в привычном для нас понимании, то алгоритмическая разрешимость или неразрешимость, сводится к проблеме остановки произвольного алгоритма решения задачи). В качестве машины-вычислителя выберем машину Тьюринга, поскольку ранее было показано, что всякая вычислимая функция реализуема на МТ и сведем решение данной задачи к существующим группам задач, для которых известно, что они решаются на МТ.

 

Случайная новость