Машина Тьюринга - помогите понять — @дневники: асоциальная сеть

суббота, 24 января 2009

14:58

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

все записи пользователя в сообществе DaZed

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

.
Ниже привожу примеры решений - можете объяснить как это получается?
Заранее благодарен

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

читать дальше

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

URL

И раз уж я сегодня такой плодовитый на записи в "дне... Ой, дайлап-дайлаа-аап, Не-е дайлааапь меня-яаа, Не-е ... Если кто не помнит классиков - о кино. С фильмами картин...

МЮHХГАУЗЕH ВСЕ ВРЕТ! Пил у Паустовского. Потом он принес новый английский наре... С утра занимался описанием природы. Особенно понравилось ...

Комментарии

24.01.2009 в 15:39

ducktales/

а я и не знаю, где ты и с кем

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

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

URL

24.01.2009 в 15:42

ducktales/

а я и не знаю, где ты и с кем

slil.ru/26577890

URL

24.01.2009 в 16:58

DaZed

Спасибо, но я что то всё равно не совсем догоняю :hmm:

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

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

URL

24.01.2009 в 17:14

Дилетант

На плечах гигантов, на спинах электронов

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, сдвигаемся вправо.... И т.д.

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

URL

24.01.2009 в 17:41

DaZed

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

URL

24.01.2009 в 17:47

Дилетант

На плечах гигантов, на спинах электронов

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

URL