一个sed写的图灵机

cjaizss 发表于 2008-05-29 20:42

还在加班，不断修改、编译数字电路
无聊中在这里看一个图灵机
该图灵机用sed编写，源码如下：

#! /bin/sed -f
#
# turing.sed -- emulate a Turing machine
#
# Christophe Blaess <ccb@club-internet.fr>
# http://perso.club-internet.fr/ccb/

# See text file for information about Turing Machine script.

# Read all the instructions, and add a final newline.
:read
N
$!b read
G

# Delete comments extending from a '#' to the end of the line.
s/#[^\n]*\n//g
s/#.*$//g

# Use a colon to separate the instructions.
s/\n/:/g

# Is there an initial tape ?
/|/ s/$.*$|$[^:]$$[^:]*$:$.*$/|\2|\3:\1\4/

# else insert a blank one.
/|/!s/$.*$/| |:\1/

# Reserve the storage place at the beginning of the pattern space,
# then set the current state to zero.
s/$.*$/0x\1/

# Start the machine !
:loop
   # Display only the tape and the state.
   h
   # (comment out the next two lines to see internal data when
   #debuging TM script)
   s/:.*//
   s/^$.$./(\1) /
   p
   g

   # Check the content of the current cell.
   /|[^:|]|/!{
            s/.*/Internal error in the Turing machine/
            q
   }

   # Store in second position the symbol read on the tape
   s/^$.$.$.*$|$.$|$.*$/\1\3\2|\3|\4/

   # Have we reached a final state ?
   /^$.$.*:\1/!{
            s/$.$.*/Final state \1 reached... end of processing/
            q
   }

   # Is there an instruction for this state and this cell content ?
   /^$..$.*:\1/!{
            s/^$.$$.$.*/No instruction for state \1 and cell \2/
            q
   }

   # Look for the new content to write.
   /^$..$.*:\1[^:|]/!{
            s/.*/I can't write this symbol on the tape!/
            q
   }
   s/^$..$$.*$|.|$.*$:\1$.$/\1\2|\4|\3:\1\4/

   # Look for the direction of movement.
   /^$..$.*:\1.[ LRlr]/!{
            s/.*/Movement must be specified as L, R or space/
            q
   }
   # Clear the substitute flag that we will use later.
   t nop
   :nop
   /^$..$.*:\1. / {
            # Direction = ' ' -> Don't move the head
            b end_move
   }
   /^$..$.*:\1./ {
            # Move the head to the left if the tape is long enough,
            s/^$..$$.*$$.$|$.$|/\1\2|\3|\4/
            t end_move
            # else extend the tape with an empty cell.
            s/|$.$|/| |\1/
            b end_move
   }

   # Move the head to the right, if the tape is long enough,
   s/|$.$|$[^:]$/\1|\2|/
   t end_move
   # else extend the tape with an empty cell.
   s/|$.$|/\1| |/

   :end_move

   # Check the new state,
   /^$..$.*:\1..[^:|]/!{
            s/.*/I can't use this symbol as new state/
            q
   }
   # then switch the machine state
   s/^$.$$.$$.*$:\1\2$..$$.$/\5\2\3:\1\2\4\5/

   # Garbage collector : cut the blank portions of the tape,
   # on the left,
   s/$..$ */\1/
   # then on the right.
   s/$..$$[^:]$ *:/\1\2:/

   b loop

###### end of the script

[ 本帖最后由 cjaizss 于 2008-5-29 21:39 编辑 ]

cjaizss 发表于 2008-05-29 21:39

改一下标题，呵呵

nicolas.shen 发表于 2008-05-30 23:32

曲高和寡:mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen:

linux_kaige 发表于 2011-12-25 00:48

我使用的sed，一般也不超过3、5行。。。

页: [1]

Chinaunix's Archiver

一个sed写的图灵机