Форум программистов, компьютерный форум, киберфорум
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
7 / 7 / 3
Регистрация: 22.09.2015
Сообщений: 165
1

Машина Тьюринга. Какой из ответов правильный?

10.01.2017, 10:06. Просмотров 262. Ответов 4
Метки нет (Все метки)

Можно ли заранее предугадать (не запустив программу), как закончится любая программа машины Тьюринга?
Варианты:
1. Нет
2. Да, если программа не закрутится в цикл
3. Да, если будет достаточно времени для исполнения программы
4. Да

Помогите, кто знает!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.01.2017, 10:06
Ответы с готовыми решениями:

К какой конфигурации придёт машина Тьюринга (исходя из начальной конфигурации)
Работа машины Тьюринга определяется следующей программой: {q}_{1}3\rightarrow {q}_{1}3L;...

Машина поста и машина тьюринга: необходимо написать алгоритм к данному изображению
нужно решение в виде команд МТ и МП

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

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

4
265 / 234 / 69
Регистрация: 23.05.2016
Сообщений: 938
10.01.2017, 10:11 2
2 и 4 друг другу не противоречат, оба правильные.
1
7 / 7 / 3
Регистрация: 22.09.2015
Сообщений: 165
10.01.2017, 10:15  [ТС] 3
Но может все таки 2 более правильный? Я вообще считал, что нет. Спасибо за ответ!
0
265 / 234 / 69
Регистрация: 23.05.2016
Сообщений: 938
10.01.2017, 11:15 4
зависит от контекста. Что называть "предсказать как закончится"?
Предсказать что программа при определенных условиях завершится или зациклится (никогда не завершится) можно для любой программы. Какой ответ кажется вам наиболее верным для программы на Паскале или С++, тот же и будет для машины Тьюринга.
1
Эксперт по математике/физике
2709 / 1858 / 626
Регистрация: 01.09.2014
Сообщений: 5,035
10.01.2017, 13:02 5
Цитата Сообщение от Aliksan Посмотреть сообщение
Можно ли заранее предугадать (не запустив программу), как закончится любая программа машины Тьюринга?
Нельзя, даже если ее запустить.

Если спрашивается, бывают ли программы, по тексту которой можно определить, остановится ли она, то ответ, естественно, да. Если спрашивается, существует ли общий способ по тексту любой программы (запуская ее или нет) определить за конечное время, остановится ли она, то ответ нет, не существует (проблема останова неразрешима). Пункт 2 вообще странный: войдет ли программа в бесконечный цикл — это как раз та информация, которую по тексту программы в общем случае определить невозможно. Если кто-то дает эту информацию сверхъестественным образом, то это меняет дело. В таком случае нужно точно определить, что значит "закрутится в цикл".

Вообще практически никакое свойство программы неразрешимо (нельзя сказать за конечное время, да или нет): теорема Райса.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.01.2017, 13:02

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

Машина Тьюринга
Добрый день, прошу всего лишь подкинуть идей, мне нужно написать ан с++ умножение и сложение 2...

Машина Тьюринга
A={a,b,c}. Приписать слева к слову P символ b (P → bP).

Машина Тьюринга
Реализовать функцию |x-y| над числами в унарном коде. Проблема - плохо представляю себе как...

Машина Тьюринга
Уважаемые люди, прошу помочь с идеей осуществления вычисления факториала числа в унарной системе. Я...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.