Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Машина Тьюринга как ее реализовать
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
igorit igorit вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.04.2010
По умолчанию Машина Тьюринга как ее реализовать - 11.05.2010, 14:33

Помогите реализовать машину Тьюринга.
Ответить с цитированием
  (#2 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.05.2010, 17:37

Цитата:
Помогите реализовать машину Тьюринга.
Реализация на примере Busy_beaver:
Код:
import Control.Monad
import Control.Monad.State


data Action = L' | R' | N'
    

type Tape a = ([a], [a])


tape s = (repeat s, repeat s)

goL ((l:ls), rs) = (ls, l:rs) 
goR (ls, (r:rs)) = (r:ls, rs)




type MT a s = (Tape a, s, (a, s) -> (a, s, Action), s -> Bool)


type MT_State a s = State (MT a s) [a]



execStepLoopMT :: MT_State a s
execStepLoopMT = do (((l:ls), r), s, ttable, halt) <- get
                    let  (t', s', a') = ttable (l, s) 
                    if halt s' then return [l]
                               else do put ((case a' of L' -> goL
                                                        R' -> goR
                                                        N' -> id) (t':ls, r), s', ttable, halt)
                                    (l:) `liftM` execStepLoopMT
                                        
execMT = execState execStepLoopMT
evalMT = evalState execStepLoopMT

makeMT :: a -> s -> ((a, s) -> (a, s, Action)) -> (s -> Bool) -> MT a s
makeMT init is table h = (tape init, is, table, h)





data MT_USR_State = A | B | C | HALT

mt_usr_halt_code :: MT_USR_State -> Bool
mt_usr_halt_code a = case a of HALT -> True
                               _    -> False

mt_usr_transition_table s = case s of (0, A) -> (1, B, R')
                                      (1, A) -> (1, C, L')
                                      (0, B) -> (1, A, L')
                                      (1, B) -> (1, B, R')
                                      (0, C) -> (1, B, L')
                                      (1, C) -> (1, HALT, N')



test  = execMT $ makeMT 0 A mt_usr_transition_table mt_usr_halt_code
test' = evalMT $ makeMT 0 A mt_usr_transition_table mt_usr_halt_code
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Машина Тьюринга Meteor Prolog 6 19.11.2011 16:53
Машина тьюринга - умножение -=GriFon=- Pascal 1 26.12.2010 21:49
Машина Тьюринга nt150789 Prolog 2 26.05.2010 23:10
Машина Тьюринга как с ней работать TuMko Алгоритмы 0 10.01.2010 17:16
Тест Тьюринга без использования FreeType Z0mSk0n PHP 1 14.11.2008 03:18
Машина Тьюринга как на ней решить задачу o1ps Алгоритмы 5 04.12.2007 21:28
Машина Тьюринга imported_Legion Задания за деньги 2 19.11.2007 02:48
Машина Тьюринга imported_Legion Prolog 9 18.05.2007 12:34
Является ли пулемет с ленточным питанием машиной Тьюринга Agent Smith Информационные технологии 1 30.08.2005 20:54
Как на assembler создать машину Тьюринга Dulsineia Assembler 1 11.12.2004 19:21
Как работать с машины Тьюринга и Поста Kelt Вопросы начинающих программистов 17 25.11.2004 23:17



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов