Машина Тьюринга - помогите понять

[DaZed]

Доброго времени суток!
В общем готовлюсь к завтрашнему экзамену по мат. логике никак не могу понять принцип построения машины Тьюринга в книгах (напр. Яблонский) как-то мудрёно все написано, а в лекциях - не до конца понятно .
Ниже привожу примеры решений - можете объяснить как это получается?
Заранее благодарен

Срок: до 25 января

@темы: Математическая логика

Comments

[ducktales/]

у нас (вмк мгу) есть очень хорошее пособие по МТ и по НАМу
сейчас скину на файлообменник и выложу

там пошагов прямо все на примерах

[ducktales/]

slil.ru/26577890

[DaZed]

Спасибо, но я что то всё равно не совсем догоняю
там в примерах заданы условия типа: "Требуется получить на ленте запись числа, которое на 1
больше числа Р." а у меня на экзе будут примеры такого типа, как я указал выше. (там задание звучит: "постройте М.Т. вычисляющую функцию")
Мне не понятно как мы узнаём куда идти: влево или вправо?
И как посчитать эти q11 ->q11R? в смысле откуда мы берём 1 и 0 и что значит запись 01...10, я так понял мы всегда начинаем отсчёт с единицы.

Сорри за множество вопросов - подсказать некому

[Дилетант]

DaZed
q с номерами — это различные состояния системы.
Всё, что у вас записано, это правила, по которым работает ваша МТ.
q1 — начальное состояние.
В вашем примере предполагается, что вначале лента стоит на значении 1, хотя на самом деле по большому счету это не всегда должно быть так. (Но не буду лишним голову засорять).

И как посчитать эти q11 ->q11R? в смысле откуда мы берём 1 и 0 и что значит запись 01...10

q₁1 -> q₁1R не "считаются".
Эта запись означает, что если мы в начальном состоянии q1 встретили единицу, то мы ее не меняем: q₁1R (т.е. была единица, она же и осталась) и смещаемся на один такт вправо: R

запись 01...10..01..10 означает записанные на ленте два числа.
Машина же представляет собой функцию от этих двух чисел.

Теперь представьте себе, что вы сами и есть эта машина. Следуйте этим инструкциям.
Инструкция q₁1 -> q₁1R будет выпоняться до тех пор, пока мы не встретим первый 0 на ленте. Так?
Сами посмотрите: встречаем 1, оставляем 1, сдвигаемся вправо; встречаем 1, оставляем 1, сдвигаемся вправо.... И т.д.

Попробуйте дальше сами.

[DaZed]

запись 01...10..01..10 означает записанные на ленте два числа

они всегда одинаковые или мы их берём по какому-либо принципу?
И когда мы начинаем шагать влево? Нужно, что-бы выполнилось какое-либо условие?

[Дилетант]

DaZed
числа абсолютно произвольны. Первое — запись х в унарной системе счисления, второе — запись у. Между ними должен быть хотя бы один 0. Это единственное требование.
Влево мы начинаем шагать, когда в правиле вместо буквы R видим букву L.

[Чудеснов]

shhhhh. на мехмате нет случайно этого пособия?

[Гость]

у нас (вмк мгу) есть очень хорошее пособие по МТ и по НАМу

А может кто-нибудь еще раз выложить это пособие на обменник, пожалуйста, до 19 января

[ducktales/]

Гость Завтра с утра буду дома и оторочено постараюсь найти

[Гость]

Ну так что, ни у кого нет?

[Гость]

Ну да ладно, не надо. Экзамен сдан.

[Гость]

Пожалуйста, перезалейте файл, хочется разобраться) Премного благодарна)

[Гость]

перезалейте файл, пожалуйста

[ducktales/]

вот пособие

[Robot]

shhhhh., спасибо большое
Зеркало

[Гость]

О_о ща пойду поизучаю
Спасибо большое!

[mpl]

Владелец дневника видит IP-адреса пользователей, оставивших комментарии!