在Erlang实现一个图灵机

Question

我有一个和实现图灵机非常相似的小项目。我所面临的基本问题是保存当前的配置，例如头部的位置和更多信息。尤其对我而言，尤其是挽救头部位置，让他向前或向后移动。 Erlang如何解决这个问题呢？

我是新来的Erlang，但据我探索OTP gen_event行为适合这一点。我的想法是通过初始头部位置，然后通过处理程序更改它。但我想有更优雅的解决方案。

Answer 1

在Erlang中，和其他函数式语言一样，你必须自己明确地管理你的状态。这意味着您必须随身携带并通过代码进行编程。它比它听起来容易得多，并很快成为第二性质。

我个人会使用gen_server行为而不是gen_event。它更具体，并将为您的机器提供更好的支持。 gen_event比你需要更普遍。 IMAO。

gen_server行为，事实上的所有行为都为管理状态提供支持。这些行为提供了顶级循环的基本功能，接收和发送消息以及管理状态。加上你想要的许多额外的好东西，即使你还不知道。

您通过提供回调函数来接口gen_server所有行为，当发生某些事情时行为会调用它。你给出了一个模块的名称，行为期望该模块包含回调。通常有一个固定数量的回调，例如gen_server有6个，具有在特定时间调用的预定义名称。

例如，有一个init/1回调，在服务器启动时调用。它执行所有特定的初始化，然后返回{ok,State}。这是您的服务器所需的状态。行为管理这个并且通过回调对它进行线程化，并期望一个新的回报。

例如，当你做一个gen_server:call(Server, Message)这将导致该服务器中的呼叫到handle_call/3回调做以以下的参数和返回值：

handle_call(Message, From, State) --> {reply,Reply,NewState} 

Reply被送回给调用者和NewState是更新的状态，然后传递到下一个回调。

您可以在文档的OTP Design Principles以及例如Gen_Server Behaviour和gen_server module部分阅读更多内容。

在你的情况下，你会让行为是图灵机管理磁带，位置等，你会发送命令给它。 IMAO阿金。

Answer 2

我认为实施取决于您的期望。您可以制作机器状态的纯功能实现。您也可以将转换表的纯功能实现作为函数或模块。最后，你可以使用OTP行为来封装任何事情。

让我们从符号开始。它可以被模拟为原子，你可以选择空白的。它可以是原子'0'。它可以是一些奇特的名字blank。如你所愿。我们可以在turing.hrl中将其定义为常量。

-define(BLANK, '0'). 

让我们继续使用磁带。一个优雅的实现是使用众所周知的zip结构。它将是三元组{LEFT, HEAD, RIGHT}。

-module(tape). 

-include("turing.hrl"). 

-export([new/0, read/1, write/2, left/1, right/1, tape2list/1]). 

new() -> {[], ?BLANK, []}. 

read({_, HEAD, _}) -> HEAD. 

write({LEFT, _, RIGHT}, HEAD) -> {LEFT, HEAD, RIGHT}. 

left({LEFT, HEAD, []})   -> {[HEAD|LEFT], ?BLANK, []}; 
left({LEFT, HEAD, [HR|RIGHT]}) -> {[HEAD|LEFT], HR, RIGHT}. 

right({[],  HEAD, RIGHT}) -> {[], ?BLANK, [HEAD|RIGHT]}; 
right({[HL|LEFT], HEAD, RIGHT}) -> {LEFT, HL, [HEAD|RIGHT]}. 

tape2list({LEFT, HEAD, RIGHT}) -> lists:reverse(LEFT, [[HEAD]|RIGHT]). 

现在我们可以让机器执行。令预期表以函数fun(STATE::any(), SYMBOL::any()) -> {NewSTATE::any(), NewSYMBOL::any(), 'left'|'right'}的形式实现，机器的状态以{STATE，TAPE}格式显示。所以转换可以建模为功能next/2。然后我们需要确定某个状态是否处于接受状态fun(STATE::any()) -> boolean()的功能，然后我们可以为模拟机器提供功能go/3，continue/3和扩展版本go/5和continue/5以及用于机器打印状态的附加参数。打印功能可以管理它自己的状态。

-module(turing_machine). 

-export([next/2, continue/5, continue/3, go/3, go/5, print_with_tape/2]). 

next({STATE, TAPE}, F) when is_function(F, 2) -> 
    {NewSTATE, NewSYMBOL, Dir} = F(STATE, tape:read(TAPE)), 
    {NewSTATE, tape:Dir(tape:write(TAPE, NewSYMBOL))}. 

continue({S, _} = St, Transition, IsAccepting, Print, PS) when 
    is_function(Transition, 2), is_function(IsAccepting, 1), is_function(Print, 2) -> 
    case IsAccepting(S) of 
    true -> St; 
    false -> 
     NSt = next(St, Transition), 
     continue(NSt, Transition, IsAccepting, Print, Print(NSt, PS)) 
    end. 

print({S, T}, _) -> 
    io:format("State: ~p, Head: ~p~n", [S, tape:read(T)]). 

print_with_tape({S, T}, _) -> 
    io:format("State: ~p, Tape: ~p~n", [S, tape:tape2list(T)]). 

continue(St, Transition, IsAccepting) -> 
    continue(St, Transition, IsAccepting, fun print/2, ok). 

go(IS, Transition, IsAccepting) -> 
    go(IS, Transition, IsAccepting, fun print/2, ok). 

go(IS, Transition, IsAccepting, Print, PS) -> 
    continue({IS, tape:new()}, Transition, IsAccepting, Print, PS). 

然后我们就可以让忙海狸机器功能

BB = fun 
    ('A', '0') -> {'B', '1', right}; 
    ('A', '1') -> {'C', '1', left}; 
    ('B', '0') -> {'A', '1', left}; 
    ('B', '1') -> {'B', '1', right}; 
    ('C', '0') -> {'B', '1', left}; 
    ('C', '1') -> {'HALT', '1', right} 
end. 

BBA = fun(S) -> S =:= 'HALT' end. 

而不是运行：

> turing_machine:go('A', BB, BBA). 
State: 'B', Head: '0' 
State: 'A', Head: '1' 
State: 'C', Head: '0' 
State: 'B', Head: '0' 
State: 'A', Head: '0' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '0' 
State: 'A', Head: '1' 
State: 'C', Head: '1' 
State: 'HALT', Head: '1' 
{'HALT',{['1'],'1',['1','1','1','1']}} 

还是更看中的：

> turing_machine:go('A', BB, BBA, fun turing_machine:print_with_tape/2, ok). 
State: 'B', Tape: [['0'],'1'] 
State: 'A', Tape: ['1',['1']] 
State: 'C', Tape: ['1','1',['0']] 
State: 'B', Tape: ['1','1','1',['0']] 
State: 'A', Tape: ['1','1','1','1',['0']] 
State: 'B', Tape: ['1','1','1',['1'],'1'] 
State: 'B', Tape: ['1','1',['1'],'1','1'] 
State: 'B', Tape: ['1',['1'],'1','1','1'] 
State: 'B', Tape: [['1'],'1','1','1','1'] 
State: 'B', Tape: [['0'],'1','1','1','1','1'] 
State: 'A', Tape: ['1',['1'],'1','1','1','1'] 
State: 'C', Tape: ['1','1',['1'],'1','1','1'] 
State: 'HALT', Tape: ['1',['1'],'1','1','1','1'] 
{'HALT',{['1'],'1',['1','1','1','1']}} 

如果您希望用机器为模块，你可以通过添加回调定义行为turing_machine工作到turing_machine.erl

-callback init_st() -> St::any(). 

-callback transition(St::any(), Symb::any()) -> 
    {NewSt::any(), NewSymb::any(), left|right}. 

-callback is_accepting(St::any()) -> boolean(). 

，还有一些附加的导出函数

-export([go_mod/1, go_mod/3, continue_mod/2, continue_mod/4]). 

及其实现

go_mod(Mod) -> 
    go_mod(Mod, fun print/2, ok). 

go_mod(Mod, Print, PS) -> 
    continue_mod(new_st(Mod:init_st()), Mod, Print, PS). 

continue_mod(St, Mod) -> 
    continue_mod(St, Mod, fun print/2, ok). 

continue_mod(St, Mod, Print, PS) -> 
    continue(St, fun Mod:transition/2, fun Mod:is_accepting/1, Print, PS). 

并且比繁忙的海狸模块

-module(busy_beaver). 

-behaviour(turing_machine). 

-include("turing.hrl"). 

-define(B, ?BLANK). 
-define(P, '1'). 

-export([init_st/0, transition/2, is_accepting/1]). 

init_st() -> 'A'. 

transition('A', ?B) -> {'B', ?P, right}; 
transition('A', ?P) -> {'C', ?P, left}; 
transition('B', ?B) -> {'A', ?P, left}; 
transition('B', ?P) -> {'B', ?P, right}; 
transition('C', ?B) -> {'B', ?P, left}; 
transition('C', ?P) -> {'HALT', ?P, right}. 

is_accepting(St) -> St =:= 'HALT'. 

然后它可以作为

> turing_machine:go_mod(busy_beaver). 
State: 'B', Head: '0' 
State: 'A', Head: '1' 
State: 'C', Head: '0' 
State: 'B', Head: '0' 
State: 'A', Head: '0' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '1' 
State: 'B', Head: '0' 
State: 'A', Head: '1' 
State: 'C', Head: '1' 
State: 'HALT', Head: '1' 
{'HALT',{['1'],'1',['1','1','1','1']}} 

甚至

> turing_machine:go_mod(busy_beaver, fun turing_machine:print_with_tape/2, ok). 
State: 'B', Tape: [['0'],'1'] 
State: 'A', Tape: ['1',['1']] 
State: 'C', Tape: ['1','1',['0']] 
State: 'B', Tape: ['1','1','1',['0']] 
State: 'A', Tape: ['1','1','1','1',['0']] 
State: 'B', Tape: ['1','1','1',['1'],'1'] 
State: 'B', Tape: ['1','1',['1'],'1','1'] 
State: 'B', Tape: ['1',['1'],'1','1','1'] 
State: 'B', Tape: [['1'],'1','1','1','1'] 
State: 'B', Tape: [['0'],'1','1','1','1','1'] 
State: 'A', Tape: ['1',['1'],'1','1','1','1'] 
State: 'C', Tape: ['1','1',['1'],'1','1','1'] 
State: 'HALT', Tape: ['1',['1'],'1','1','1','1'] 
{'HALT',{['1'],'1',['1','1','1','1']}} 

然后你就可以选择让它在一个或其他方式处理或OTP工人。