|
Машина Тьюринга
|
|
| Saitei | Дата: Четверг, 22 Мая 2014, 15:55 | Сообщение # 1 |
|
старожил
Сейчас нет на сайте
| Кто-нибудь писал такую на C++/C/java/etc.?
|
|
|
| |
| vasua99 | Дата: Пятница, 23 Мая 2014, 12:05 | Сообщение # 2 |
GNU follower
Сейчас нет на сайте
| А разве язык имеет значение? По моему, принципы строения машины Тьюринга одни и те, же)
Жизнь игра, и мы в ней пешки... А я кушаю пельмешки)
|
|
|
| |
| -l33t-h4xx- | Дата: Пятница, 23 Мая 2014, 14:34 | Сообщение # 3 |
участник
Сейчас нет на сайте
| Если интерпретатор брейнфака считать за таковую, то конечно.
А что?
Как правильно задавать вопросы
|
|
|
| |
| Saitei | Дата: Суббота, 24 Мая 2014, 12:19 | Сообщение # 4 |
|
старожил
Сейчас нет на сайте
| -l33t-h4xx-, в универе частично начали проходить эту машину. Я продвинулся чуть дальше, чем все... Хочется попрограммировать такую машинку, но не знаю на чём)
|
|
|
| |
| vasua99 | Дата: Суббота, 24 Мая 2014, 12:56 | Сообщение # 5 |
|
GNU follower
Сейчас нет на сайте
| Да на любом языке который знаешь. Разницы в принципе вообще нет)
А вообще попробуй написать интерпретатор brainf***а. Это уже машина Тьюринга. Далее можешь написать пару встроенных функций, потом парсер, синтаксический лексер для своего мини-языка. Синтаксический лексер строит AST и отправляет его машине Тьюринга. Как то занимался подобной фигней.
P.S совет - если все это делать, то без графов и автоматов не обойтись(не тех, которые АК,а те.. ну в общем поняли))
Жизнь игра, и мы в ней пешки... А я кушаю пельмешки)
|
|
|
| |
| -l33t-h4xx- | Дата: Суббота, 24 Мая 2014, 17:47 | Сообщение # 6 |
|
участник
Сейчас нет на сайте
| Цитата vasua99 (  ) то без графов и автоматов не обойтись
Опять ты пугаешь! Там же не нужно так много суровой теории.
Как правильно задавать вопросы
|
|
|
| |
| Xakep | Дата: Суббота, 24 Мая 2014, 18:07 | Сообщение # 7 |
めちゃくちゃちゃ
Сейчас нет на сайте
| Цитата vasua99 ( ) P.S совет - если все это делать, то без графов и автоматов не обойтись(не тех, которые АК,а те.. ну в общем поняли))
я точно не помню как работает машина тьюринга, но помню что там ничего сложного, и думаю никаких графов и автоматов не нужно.
на счет интерпретатора, то там конечные автоматы только в лексическом анализаторе (и то у меня в яп их только 2 было), ну а графы и тем более не нужны. Хотя если речь идет об оптимизации промежуточного и backend кода, то там и автоматы, и разные диаграммы переходов и конечные автоматы, короче там уже начинается довольно сложная математика.
|
|
|
| |
| Saitei | Дата: Воскресенье, 25 Мая 2014, 00:48 | Сообщение # 8 |
|
старожил
Сейчас нет на сайте
| Цитата vasua99 ( ) Да на любом языке который знаешь. Разницы в принципе вообще нет)
А вообще попробуй написать интерпретатор brainf***а. Это уже машина Тьюринга. Далее можешь написать пару встроенных функций, потом парсер, синтаксический лексер для своего мини-языка. Синтаксический лексер строит AST и отправляет его машине Тьюринга. Как то занимался подобной фигней.
P.S совет - если все это делать, то без графов и автоматов не обойтись(не тех, которые АК,а те.. ну в общем поняли))
с графами я дружу, а вот как строить AST я никогда не понимал... Пытался понять, но, видимо, пока что это свыше моих сил. Ну а покодить ан машинке Тьюринга хочется 
-l33t-h4xx-, vasua99, я считаю, что Brainfuck это нечто похожее на машину Тьюринга. Но это не машина Тьюринга...
Если я ничего не путаю, то машина Тьюринга программируется подачей N строк (по 5 символов на строку).
1 символ: внутреннее состояние, в котором машина сейчас находится
2 символ: элемент считываемой ячейки
3 символ: новое внутр. состояние
4 символ: символ, который машина печатает
5 символ: куда движемся (влево\вправо\STOP)
В брейнфаке действительно есть что-то вроде ленты с такими же ячейками и пр, но он крайне нечитабелен( глаз вырвать можно..
|
|
|
| |
| vasua99 | Дата: Среда, 28 Мая 2014, 12:42 | Сообщение # 9 |
|
GNU follower
Сейчас нет на сайте
| Ну в принципе ничего тяжелого. Читаем построчно и выполняем необходимое. Если будет чуть позже время - напишу и скину. Сейчас к экзамену готовится надо. Через 2 дня писать(
Жизнь игра, и мы в ней пешки... А я кушаю пельмешки)
|
|
|
| |
| Saitei | Дата: Пятница, 30 Мая 2014, 15:23 | Сообщение # 10 |
|
старожил
Сейчас нет на сайте
| S0 # S1 # R
S1 1 S2 # R
S1 0 S7 # R
S2 1 S2 1 R
S2 0 S3 0 R
S3 1 S4 0 R
S3 0 S3 0 R
S4 1 S4 1 R
S4 0 S4 0 R
S4 # S5 0 R
S5 # S6 # L
S6 0 S6 0 L
S6 1 S6 1 L
S6 # S1 # R
S7 0 S7 1 R
S7 # SQUIT # STOP
#11011#
##1011#
##1011#
##1011#
##1001#
##1001#
##10010#
##10010#
##10010#
##10010#
##10010#
##10010#
##10010#
###0010#
###0010#
###0010#
###0000#
###0000#
###00000#
###00000#
###00000#
###00000#
###00000#
###00000#
###00000#
####0000#
####1000#
####1100#
####1110#
####1111#
####1111#Добавлено (30.05.2014, 15:23)
---------------------------------------------
Ах да, это я написал прогу x*y (Здесь это 2*2 (т.е. 11*11 (#11011#)))
|
|
|
| |
