Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
1

Построить машину Тьюринга для вычисления функции (x,y,z)=у

24.05.2018, 21:17. Просмотров 922. Ответов 16
Метки нет (Все метки)

Задание: Построить машину Тьюринга для вычисления функции (x,y,z)=у

я немного не понимаю: у меня есть пример: Построить машину Тьюринга для вычисления функции (x,y,z)=z

такое решение:
g0 1 g0 0 R
g0 0 g1 0 R
g1 1 g1 0 R
g1 0 g2 0 R почему g0 1? я вот этого вобще не понимаю
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2018, 21:17
Ответы с готовыми решениями:

построить машину Тьюринга в алфавите {a0, *, 1} для вычисления функции f(n)=2n
Приветствую всех! если нетрудно, помогите решить, совсем плохо логика работает( не доходит(

Построить машину Тьюринга для функции
Исправьте ошибки Построить машину тьюринга для функции: f(x)=x+1, в троичной системе счисления

Построить машину Тьюринга для функции
Необходимо построить машину Тьюринга для функции f(x) = x-26: Подскажите, что писать в состояния...

Построить машину Тьюринга для следующей функции f(x,y)=2y-2x
Помогите, пожалуйста, построить машину Тьюринга для следующей функции f(x,y)=2y-2x. И какая...

Построить машину Тьюринга для функции f(x) = !X + Y (исключающее или)
Требуется построить принцип работы машина Тьюринга для функции f(x) = !X + Y (исключающее или)...

16
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 22:05 2
Насколько я понимаю, x, y, z представляют собой последовательности единиц, разделенные одним нулем. Программа, которую вы привели, стирает первые две группы единиц и оставляет третью. И, возможно, состояния обозначаются через q, а не g (я такое обозначение встречал чаще).
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 22:09  [ТС] 3
да,вы правы,а можно у вас узнать тогда получается g0 1 во всех 3 случаях, вот у меня есть решение для моего вопроса

q0 1 q0 0 R

g0 0 g1 0 R

g1 1 g1 0 R

g1 0 g2 0 R у меня вопрос почему у нас идёт в первой строчке дублирование,как я понимаю мы на ленте,ползунок у нас на 1 и мы идём вправо, почему мы из q0 1 вернули в g0 0, возможно это всё на поверхности лежит,но я человек глупый,честно понимаю слабо очень,надеюсь вы мне подскажите),я знаю теорию но я совершенно не понимаю практику
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 22:29 4

Не по теме:

Пишите, пожалуйста, короткими полными предложениями. Не надо потока из десятка мыслей, разделенных запятыми.



Цитата Сообщение от Darkyn555 Посмотреть сообщение
у меня есть решение для моего вопроса
q0 1 q0 0 R
g0 0 g1 0 R
g1 1 g1 0 R
g1 0 g2 0 R
Чем это решение отличается от программы для функции f(x, y, z) = z из сообщения 1?

Цитата Сообщение от Darkyn555 Посмотреть сообщение
почему мы из q0 1 вернули в g0 0
Пока головка машины находится в первой группе единиц, машина в состоянии q0. Во второй группе единиц машина в состоянии q1, в третьей — в q2. Команда q0 1 q0 0 R означает, что единицы из первой группы переписываются нулями (то есть пробелами).
0
24.05.2018, 22:29
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 22:45  [ТС] 5
Тогда получается что строчка g0 0 g1 0 R это 2 набор и тут мы тоже делаем 0,так как у нас функция (x y z)=z

а в следующей 3 строчке g1 1 g1 0 R почему тут дубляж если у нас 1 в g1,тут ведь нам не нужны пробелы? Я сейчас читаю теорию,нашёл книгу и пытаюсь разобраться

Добавлено через 10 минут
А строчка
g0 0 g1 0 R
показывает что машина после того,как сделал везде 0 переходит на 2 строчку на 0? а почему тогда там становится 1?
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 22:47 6
Цитата Сообщение от Darkyn555 Посмотреть сообщение
Тогда получается что строчка g0 0 g1 0 R это 2 набор
Строчка g0 0 g1 0 R — это команда, а второй набор — это группа единиц на ленте. Команда машины Тьюринга и слово на ленте — это разные вещи.

Цитата Сообщение от Darkyn555 Посмотреть сообщение
а в следующей 3 строчке g1 1 g1 0 R почему тут дубляж
"А в следующей 3 строчке g1 1 g1 0 R". ТОЧКА. С большой буквы: "Почему тут дубляж?". Дубляж — это повторение. Повторение чего?

Цитата Сообщение от Darkyn555 Посмотреть сообщение
если у нас 1 в g1
Я не понимаю фразу "1 в g1".

Цитата Сообщение от Darkyn555 Посмотреть сообщение
тут ведь нам не нужны пробелы?
Хорошо бы еще понимать, что вы имеете в виду под "тут".

Если хотите, чтобы вас понимали, вам нужно писать намного, НАМНОГО точнее.
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 22:54  [ТС] 7
Извиняюсь,сейчас я распишу,мне не совсем понятно вот это:
q0 1 q0 1 R
g0 0 g1 0 R вот эти команды показывают что у нас 1 группа 0, тогда g1 1 g1 0 R вот это 2 группа,тут мы тоже заменили на 0
и получается 3 группа,нам нужны там 1, а в решении g1 0 g2 0 R вот там 0

Добавлено через 42 секунды
Просто у нас вобще не было теории практически,поэтому я вобще дуб
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 23:06 8
Используйте или только q, или только g для обозначения состояний. Лучше q.

Цитата Сообщение от Darkyn555 Посмотреть сообщение
q0 1 q0 1 R
В предыдущих сообщениях была команда q0 1 q0 0 R. Это потому, что первую группу единиц нужно превратить в нули.

Цитата Сообщение от Darkyn555 Посмотреть сообщение
и получается 3 группа,нам нужны там 1, а в решении g1 0 g2 0 R вот там 0
Когда головка в состоянии q1 находится под нулем, отделяющим вторую и третью группы единиц, то машина переходит в состояние q2, оставляет этот ноль без изменений, двигается вправо (под первую единицу третьей группы) и останавливается (поскольку команд с начальным состоянием q2 нет).
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 23:11  [ТС] 9
С первой строчкой разобрался, тогда вопрос по 2 строчке: g0 0 g1 0 R , тут ползунок получается ползунок переходит на 0,который находится между 1 и 2 группами,верно?
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 23:13 10
Нет, он с нуля двигается вправо, оставляя ноль без изменений.
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 23:15  [ТС] 11
то есть получается первой строчкой мы сделали 0, вторая строчка двигает ползунок вправо, не меняя 0 на 1, а 3 строчка:
g1 1 g1 0 R показывает что ползунок находится на 1 у второй группы и тут мы по аналогии делаем у 2 группы 0,верно?
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 23:30 12
Цитата Сообщение от Darkyn555 Посмотреть сообщение
и тут мы по аналогии делаем у 2 группы 0,верно?
Да, команда q1 1 q1 0 R заменяет вторую группу единиц на нули.
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 23:37  [ТС] 13
То есть получается мы 1 командой заменили на 1 на 0, вторая строчка показывает что когда мы видим 0 то переходим на q1 и стирается вся группа x,верно?
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
24.05.2018, 23:41 14
Цитата Сообщение от Darkyn555 Посмотреть сообщение
вторая строчка показывает что когда мы видим 0 то переходим на q1 и стирается вся группа x,верно?
Не знаю, что вы имеете в виду под "всей группой x". Вторая команда q0 0 q1 0 R переводит головку из-под нуля, разделяющего первую и вторую группу единиц, под первую единицу второй группы.
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
24.05.2018, 23:46  [ТС] 15
всё понял),вроде разобрался,спасибо вам большое)
0
Darkyn555
0 / 0 / 0
Регистрация: 02.05.2018
Сообщений: 22
27.05.2018, 14:31  [ТС] 16
Вот смотрите: у меня решение не приняли,я написал новое,нужно чтобы головка возвратилась в начало, верно вот это вот?
f(x,y,z)=y
q0 1 q0 0 R
q0 0 q1 0 R
q1 1 q1 0 R
q1 0 q2 0 R
q2 1 q2 0 R
q2 0 q3 0 R
q3 0 q3 0 L
q3 1 q4 1 L
q4 1 q4 1 L
q4 0 q5 0 R
0
3D Homer
Эксперт по математике/физике
2203 / 1498 / 507
Регистрация: 01.09.2014
Сообщений: 3,818
28.05.2018, 21:19 17
Промоделируйте поведение этой машины вручную (только совершенно формально, а не интуитивно) на входе из трех групп единиц, разделенных двумя нулями. Действительно ли эта программа оставляет среднюю группу?
0
28.05.2018, 21:19
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2018, 21:19

Построить Машину Тьюринга, вычисляющую значение функции f(x)=x-y
Здравствуйте!Помогите пожайлуста, очень нужна помошь :( Построить Машину Тьюринга,вычисляющую...

Построить машину Тьюринга, вычисляющую след функции
Требуется построить машину Тьюринга, вычисляющую след функции: а) f(x,y)=0, если x=0 и =x-1, если...

Построить Машину Тьюринга, вычисляющую значение функции
Помогите, пожалуйста, построить машину Тьюринга для f(x,y)=2x+y


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

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

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