Здравствуйте,я учусь заочно, и у меня задание по Машине Тьюринга,нужно построить для функции (x,y,z)=z я нашёл готовое решение,но я его не понимаю вобще,

как выглядит вобще лента?у меня полкчается что 1..1 0 1..1 0 1...1, мы убираем 2 группы и получается 1..1, так чтолле? тогда как будет выглядеть лента как будет выглдеть лента для фкнкции (x,y,z)= y и (x,y,z)= x так же чтолле ? мне бы хотя бы понять как лента выглядит)

задан 24 Май 22:36

Лента разбита на ячейки -- подобно полоске на клетчатой бумаге. В каждой ячейке написано 1 или 0. Число задаётся в виде 1...1 (оно равно количеству 1; иногда с увеличением на один, то есть "два" удобно задавать как 111). Если несколько чисел, то они даются через пробел. Все три задачи аналогичны: надо оставить единички одной группы, а остальное стереть.

(24 Май 22:56) falcao

а можно ещё пару вопросов тогда у вас уточнить,тогда получается g0 1 во всех 3 случаях, вот у меня есть решение для моего вопроса

q0 1 q0 1 R

g0 0 g1 0 R

g1 1 g1 0 R

g1 0 g2 0 R у меня вопрос почему у нас идёт в первой строчке дублирование,как я понимаю мы на ленте,ползунок у нас на 1 и мы идём вправо, почему мы из q0 1 вернули в g0 0, возможно это всё на поверхности лежит,но я человек глупый,честно понимаю слабо очень,надеюсь вы мне подскажите

(24 Май 23:03) darkyn

@darkyn: q0 есть внутреннее состояние машины. Оно не меняется, если мы продолжаем делать одно и то же. Например, двигаться вправо, пока видим на ленте 1. Если речь о вычислении функции f(x,y,z)=z, то первая группа единиц должна стираться, и тогда команда (выполняемая многократно), имеет вид q0 1 q0 0 R.

Вообще, почитайте теорию, потому что без понимания основ что-либо делать трудно. Например, глава 5 параграф 2 учебника Мендельсона. Там всего-то надо прочитать страницы две-три.

(24 Май 23:10) falcao

Хорошо,я сейчас почитаю,если будут вопросы,то тут напишу

(24 Май 23:11) darkyn

вот я верно понимаю?,У нас в первой строчке:q0 1 q0 0 R. машина стирает 1 и пишет 0, и означает все единицы в первой группе будут 0, идём дальше, q0 1 q0 1 R

g0 0 g1 0 R вот эти команды стирают первую группы и мы переходим на 2 группу

g1 1 g1 0 R?

(24 Май 23:47) darkyn
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,541
×61

задан
24 Май 22:36

показан
73 раза

обновлен
24 Май 23:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru