Turing Machine
A Turing Machine is a theoretical machine that resembles a very primitive computing device. A TM is composed of an infinitely long tape, and a head that can read and write from and to it. Every 'step', the Turing Machine reads from the tape, and based on the symbol and the current machine 'state', moves the head forward or backward along the tape, and changes the tape, if need be. While this seems extremely limited, these are the fundamental functions of computation, and using only these functions, a large-enough Turing Machine is capable of solving any problem that a supercomputer can solve. The Wikipedia article on Turing Machines is an excellent place to learn more about them.
Functions:
and(),
ansi(),
art(),
attrib_set(),
dec(),
eq(),
grab(),
gt(),
hasattr(),
ibreak(),
if(),
inc(),
isint(),
iter(),
ljust(),
lnum(),
max(),
mid(),
min(),
money(),
regmatch(),
setq(),
setr(),
space(),
strlen(),
strreplace(),
switch(),
u(),
v().
Compatibility:
PennMUSH.
Instructions
Copy and paste the below code into a compatible MUSH or MUX.
MUSHCode for Turing Machine
@create Turing Machine
@lock/Basic Turing Machine==me
@lset Turing Machine/Basic=no_inherit
@set Turing Machine = VISUAL
@set Turing Machine = !NO_COMMAND
&ACT_LOOP Turing Machine=@switch [and(gt(v(TM_CREDIT),0),hasattr(me,TM_Q[u(TM_STATE)]))]=1,{@trigger me/ACT_STEP;&TM_CREDIT me = [dec(v(TM_CREDIT))];@wait 5=@trigger me/ACT_LOOP},{@emit The Turing Machine stops running.;&TM_CREDIT me=0}
&ACT_STEP Turing Machine=think [if(and(regmatch(setr(0,grab(v(TM_Q[v(TM_STATE)]),mid(v(TM_TAPE),v(TM_HEAD),1)*)),^\[a-zA-Z0-9_\]\[a-zA-Z0-9_\]\[LR\]\(\[0-9\]\[0-9\]?|\[AR\]\)$),isint(v(TM_STATE))),0,setq(0,xxRR))];&TM_TAPE me=[strreplace(v(TM_TAPE),v(TM_HEAD),1,mid(%q0,1,1))];;&TM_HEAD me=[switch(mid(%q0,2,1),L,[max(0,dec(v(TM_HEAD)))],R,[min(inc(v(TM_HEAD)),dec(strlen(v(TM_TAPE))))],v(TM_HEAD))];&TM_STATE me=[mid(%q0,3,strlen(%q0))];@emit The Turing Machine [switch(v(TM_STATE),A,[ansi(hg,accepts)] the input,R,[ansi(hr,rejects)] the input,is working)].%rIt now reads: [u(VAR_STAT)]
&APAYMENT Turing Machine=@assert [eq(v(TM_CREDIT),0)];&TM_CREDIT me=10;@trigger me/ACT_LOOP
@set Turing Machine/APAYMENT=no_command prefixmatch
&COM_CLEAR Turing Machine=$+tm/clear: think [iter(lnum(100),if(hasattr(me,TM_Q##),attrib_set(me/TM_Q##),ibreak()))];@emit Transition table cleared.
&COM_EXAMPLE Turing Machine=$+tm/example:&TM_CREDIT me=0;&TM_STATE me=0;&TM_HEAD me=0;&TM_TAPE me=10001_____;&TM_OTAPE me=10001_____;&TM_Q0 me=1xR1;&TM_Q1 me=0xR1 1xR2;&TM_Q2 me=__LA;&TM_Q3 me;@emit The Turing Machine has been programmed to accept input that matches the%rregular expression '10*1'. Use 'give 1 to Turing Machine' to try it on the%rstring on the tape already. Use '+tm/tape <string>' to create your own tape%rfor the machine to solve (make sure you end it with at least one '_' symbol).%rTo look at the configuration, use '+tm/view'.
&COM_HELP1 Turing Machine=$+tm/help:@pemit %#=[u(HELP_DEFAULT)]
&COM_HELP2 Turing Machine=$+tm/help *:@switch [hasattr(me,HELP_%0)]=1,@pemit %#=[u(HELP_%0)],@pemit %#=No such help topic.
&COM_RESET Turing Machine=$+tm/reset:&TM_HEAD me=0;&TM_STATE me=0;&TM_TAPE me=[v(TM_OTAPE)];&TM_CREDIT me=0;@emit Turing Machine reset.
&COM_SET Turing Machine=$+tm/set *=*:@switch [and(regmatch(%0,^\[0-9\]\[0-9\]?$),regmatch(%1,\(\\b\[a-zA-Z0-9_\]\[a-zA-Z0-9_\]\[LR\]\(\[0-9\]+|\[AR\]\)\\b\)+))]=1,{&TM_Q%0 me=%1;@emit Q%0 set.},@pemit %#=There was an error in your state string. See +tm/help for more info.
&COM_TAPE Turing Machine=$+tm/tape *:@switch [regmatch(%0,^\[a-zA-Z0-9_\]+$)]=1,{&TM_TAPE me=%0;&TM_OTAPE me=%0;&TM_HEAD me=[min(dec(strlen(%0)),v(TM_HEAD))];@emit Tape set.},@pemit %#=Strings may only contain a-z, A-Z, 0-9, and _.
&COM_UNSET Turing Machine=$+tm/unset *:@switch [regmatch(%0,^\[0-9\]\[0-9\]?$)]=1,{&TM_Q%0 me;@emit Q%0 cleared.},@pemit %#=No such state.
&COM_VIEW Turing Machine=$+tm/view:@pemit %#=Turing Machine%rState: [v(TM_STATE)]%rTape: [u(VAR_STAT)][iter(lnum(100),if(hasattr(me,TM_Q##),%r Q[ljust(##,2)]: [v(TM_Q##)],ibreak()))]
&COST Turing Machine=1
@set Turing Machine/COST=no_command prefixmatch
&DESCRIBE Turing Machine=It's [art(money(1))] [money(1)]-operated Turing Machine[switch(v(TM_STATE),A,%bin the [ansi(hg,accept)] state,R,%bin the [ansi(hr,reject)] state,)].%rThe tape currently reads: [u(VAR_STAT)]%rUse '+tm/help' to find out about how to use it.
@set Turing Machine/DESCRIBE=no_command visual prefixmatch public nearby
&HELP_AUTHOR Turing Machine=%rThis program was written by Markus from M*U*S*H. You're free to use it however%ryou like - study it, modify it, sell it - I don't care. I've set the object%rVISUAL, so you should be able to @decompile it or examine it and get all the%rsource code. If you like it or have any comments about it, send me some @mail.%r
&HELP_BUGS Turing Machine=%r+tm/view and +tm/clear only work on sequential states (for efficiency).%r
&HELP_COMMANDS Turing Machine=%r+tm/view: Look at the state of the TM and the transition table.%r+tm/reset: Reset the state, head, and tape.%r+tm/clear: Clear the transition table.%r+tm/tape <string>: Initialize the (finite) tape. The tape may only contain%r[space(19)]the characters 0, 1, and _.%r+tm/set <Q>=<transitions>: Set transitions for state Q. See '+tm/help transitions'%r+tm/unset <Q>: Clear the transitions for Q.%r+tm/example: Set the machine up to an example configuration.%r
&HELP_DEFAULT Turing Machine=%rTopics:%r overview - What are Turing Machines (TMs) anyway?%r commands - Commands for this TM%r transitions - Programming this TM%r bugs - Problems I already know about%r author - Copyright and Stuff%r
&HELP_OVERVIEW Turing Machine=A Turing Machine is a theoretical machine that resembles a very primitive%rcomputing device. A TM is composed of an infinitely long tape, and a head%rthat can read and write from and to it. Every 'step', the Turing Machine reads%rfrom the tape, and based on the symbol and the current machine 'state', moves%rthe head forward or backward along the tape, and changes the tape, if need be.%rWhile this seems extremely limited, these are the fundamental functions of%rcomputation, and using only these functions, a large-enough Turing Machine is%rcapable of solving any problem that a supercomputer can solve. The Wikipedia%rarticle on Turing Machines is an excellent place to learn more about them.
&HELP_TRANSITIONS Turing Machine=%rA transition for a state is represented as a list of strings in the form WXYZ.%rW is the character that is currently on the tape under the head. X is the%rcharacter that should be written to the tape (a-z, A-Z, 0-9, or _) Y is the%rdirection that the head should move after writing (should be L or R) Z is the%rstate of the machine after moving the head. This should either be a number%rfrom 0-99, A (the accept state), or R (the reject state). Should the state in%rquestion be undefined, it is assumed to be a transition to the Reject state.%rLook at +tm/example to see a working example program.%r
&OPAYMENT Turing Machine=drops [art(money(1))] [money(1)] into the Turing Machine.
@set Turing Machine/OPAYMENT=no_command prefixmatch
&PAYMENT Turing Machine=You drop [art(money(1))] [money(1)] into the Turing Machine.
@set Turing Machine/PAYMENT=no_command prefixmatch
&TM_CREDIT Turing Machine=0
@set Turing Machine/TM_CREDIT=no_command
&TM_HEAD Turing Machine=4
&TM_OTAPE Turing Machine=10001_____
@set Turing Machine/TM_OTAPE=no_command
&TM_Q0 Turing Machine=1xR1
@set Turing Machine/TM_Q0=no_command
&TM_Q1 Turing Machine=0xR1 1xR2
@set Turing Machine/TM_Q1=no_command
&TM_Q2 Turing Machine=__LA
@set Turing Machine/TM_Q2=no_command
&TM_STATE Turing Machine=A
&TM_TAPE Turing Machine=xxxxx_____
&VAR_STAT Turing Machine=[ansi(h,strreplace(v(TM_TAPE),v(TM_HEAD),1,[ansi(i,mid(v(TM_TAPE),v(TM_HEAD),1
look Turing Machine
@lock/Basic Turing Machine==me
@lset Turing Machine/Basic=no_inherit
@set Turing Machine = VISUAL
@set Turing Machine = !NO_COMMAND
&ACT_LOOP Turing Machine=@switch [and(gt(v(TM_CREDIT),0),hasattr(me,TM_Q[u(TM_STATE)]))]=1,{@trigger me/ACT_STEP;&TM_CREDIT me = [dec(v(TM_CREDIT))];@wait 5=@trigger me/ACT_LOOP},{@emit The Turing Machine stops running.;&TM_CREDIT me=0}
&ACT_STEP Turing Machine=think [if(and(regmatch(setr(0,grab(v(TM_Q[v(TM_STATE)]),mid(v(TM_TAPE),v(TM_HEAD),1)*)),^\[a-zA-Z0-9_\]\[a-zA-Z0-9_\]\[LR\]\(\[0-9\]\[0-9\]?|\[AR\]\)$),isint(v(TM_STATE))),0,setq(0,xxRR))];&TM_TAPE me=[strreplace(v(TM_TAPE),v(TM_HEAD),1,mid(%q0,1,1))];;&TM_HEAD me=[switch(mid(%q0,2,1),L,[max(0,dec(v(TM_HEAD)))],R,[min(inc(v(TM_HEAD)),dec(strlen(v(TM_TAPE))))],v(TM_HEAD))];&TM_STATE me=[mid(%q0,3,strlen(%q0))];@emit The Turing Machine [switch(v(TM_STATE),A,[ansi(hg,accepts)] the input,R,[ansi(hr,rejects)] the input,is working)].%rIt now reads: [u(VAR_STAT)]
&APAYMENT Turing Machine=@assert [eq(v(TM_CREDIT),0)];&TM_CREDIT me=10;@trigger me/ACT_LOOP
@set Turing Machine/APAYMENT=no_command prefixmatch
&COM_CLEAR Turing Machine=$+tm/clear: think [iter(lnum(100),if(hasattr(me,TM_Q##),attrib_set(me/TM_Q##),ibreak()))];@emit Transition table cleared.
&COM_EXAMPLE Turing Machine=$+tm/example:&TM_CREDIT me=0;&TM_STATE me=0;&TM_HEAD me=0;&TM_TAPE me=10001_____;&TM_OTAPE me=10001_____;&TM_Q0 me=1xR1;&TM_Q1 me=0xR1 1xR2;&TM_Q2 me=__LA;&TM_Q3 me;@emit The Turing Machine has been programmed to accept input that matches the%rregular expression '10*1'. Use 'give 1 to Turing Machine' to try it on the%rstring on the tape already. Use '+tm/tape <string>' to create your own tape%rfor the machine to solve (make sure you end it with at least one '_' symbol).%rTo look at the configuration, use '+tm/view'.
&COM_HELP1 Turing Machine=$+tm/help:@pemit %#=[u(HELP_DEFAULT)]
&COM_HELP2 Turing Machine=$+tm/help *:@switch [hasattr(me,HELP_%0)]=1,@pemit %#=[u(HELP_%0)],@pemit %#=No such help topic.
&COM_RESET Turing Machine=$+tm/reset:&TM_HEAD me=0;&TM_STATE me=0;&TM_TAPE me=[v(TM_OTAPE)];&TM_CREDIT me=0;@emit Turing Machine reset.
&COM_SET Turing Machine=$+tm/set *=*:@switch [and(regmatch(%0,^\[0-9\]\[0-9\]?$),regmatch(%1,\(\\b\[a-zA-Z0-9_\]\[a-zA-Z0-9_\]\[LR\]\(\[0-9\]+|\[AR\]\)\\b\)+))]=1,{&TM_Q%0 me=%1;@emit Q%0 set.},@pemit %#=There was an error in your state string. See +tm/help for more info.
&COM_TAPE Turing Machine=$+tm/tape *:@switch [regmatch(%0,^\[a-zA-Z0-9_\]+$)]=1,{&TM_TAPE me=%0;&TM_OTAPE me=%0;&TM_HEAD me=[min(dec(strlen(%0)),v(TM_HEAD))];@emit Tape set.},@pemit %#=Strings may only contain a-z, A-Z, 0-9, and _.
&COM_UNSET Turing Machine=$+tm/unset *:@switch [regmatch(%0,^\[0-9\]\[0-9\]?$)]=1,{&TM_Q%0 me;@emit Q%0 cleared.},@pemit %#=No such state.
&COM_VIEW Turing Machine=$+tm/view:@pemit %#=Turing Machine%rState: [v(TM_STATE)]%rTape: [u(VAR_STAT)][iter(lnum(100),if(hasattr(me,TM_Q##),%r Q[ljust(##,2)]: [v(TM_Q##)],ibreak()))]
&COST Turing Machine=1
@set Turing Machine/COST=no_command prefixmatch
&DESCRIBE Turing Machine=It's [art(money(1))] [money(1)]-operated Turing Machine[switch(v(TM_STATE),A,%bin the [ansi(hg,accept)] state,R,%bin the [ansi(hr,reject)] state,)].%rThe tape currently reads: [u(VAR_STAT)]%rUse '+tm/help' to find out about how to use it.
@set Turing Machine/DESCRIBE=no_command visual prefixmatch public nearby
&HELP_AUTHOR Turing Machine=%rThis program was written by Markus from M*U*S*H. You're free to use it however%ryou like - study it, modify it, sell it - I don't care. I've set the object%rVISUAL, so you should be able to @decompile it or examine it and get all the%rsource code. If you like it or have any comments about it, send me some @mail.%r
&HELP_BUGS Turing Machine=%r+tm/view and +tm/clear only work on sequential states (for efficiency).%r
&HELP_COMMANDS Turing Machine=%r+tm/view: Look at the state of the TM and the transition table.%r+tm/reset: Reset the state, head, and tape.%r+tm/clear: Clear the transition table.%r+tm/tape <string>: Initialize the (finite) tape. The tape may only contain%r[space(19)]the characters 0, 1, and _.%r+tm/set <Q>=<transitions>: Set transitions for state Q. See '+tm/help transitions'%r+tm/unset <Q>: Clear the transitions for Q.%r+tm/example: Set the machine up to an example configuration.%r
&HELP_DEFAULT Turing Machine=%rTopics:%r overview - What are Turing Machines (TMs) anyway?%r commands - Commands for this TM%r transitions - Programming this TM%r bugs - Problems I already know about%r author - Copyright and Stuff%r
&HELP_OVERVIEW Turing Machine=A Turing Machine is a theoretical machine that resembles a very primitive%rcomputing device. A TM is composed of an infinitely long tape, and a head%rthat can read and write from and to it. Every 'step', the Turing Machine reads%rfrom the tape, and based on the symbol and the current machine 'state', moves%rthe head forward or backward along the tape, and changes the tape, if need be.%rWhile this seems extremely limited, these are the fundamental functions of%rcomputation, and using only these functions, a large-enough Turing Machine is%rcapable of solving any problem that a supercomputer can solve. The Wikipedia%rarticle on Turing Machines is an excellent place to learn more about them.
&HELP_TRANSITIONS Turing Machine=%rA transition for a state is represented as a list of strings in the form WXYZ.%rW is the character that is currently on the tape under the head. X is the%rcharacter that should be written to the tape (a-z, A-Z, 0-9, or _) Y is the%rdirection that the head should move after writing (should be L or R) Z is the%rstate of the machine after moving the head. This should either be a number%rfrom 0-99, A (the accept state), or R (the reject state). Should the state in%rquestion be undefined, it is assumed to be a transition to the Reject state.%rLook at +tm/example to see a working example program.%r
&OPAYMENT Turing Machine=drops [art(money(1))] [money(1)] into the Turing Machine.
@set Turing Machine/OPAYMENT=no_command prefixmatch
&PAYMENT Turing Machine=You drop [art(money(1))] [money(1)] into the Turing Machine.
@set Turing Machine/PAYMENT=no_command prefixmatch
&TM_CREDIT Turing Machine=0
@set Turing Machine/TM_CREDIT=no_command
&TM_HEAD Turing Machine=4
&TM_OTAPE Turing Machine=10001_____
@set Turing Machine/TM_OTAPE=no_command
&TM_Q0 Turing Machine=1xR1
@set Turing Machine/TM_Q0=no_command
&TM_Q1 Turing Machine=0xR1 1xR2
@set Turing Machine/TM_Q1=no_command
&TM_Q2 Turing Machine=__LA
@set Turing Machine/TM_Q2=no_command
&TM_STATE Turing Machine=A
&TM_TAPE Turing Machine=xxxxx_____
&VAR_STAT Turing Machine=[ansi(h,strreplace(v(TM_TAPE),v(TM_HEAD),1,[ansi(i,mid(v(TM_TAPE),v(TM_HEAD),1
look Turing Machine