时间戳

首页 > 解决方案 > 在 Haskell 中生成一个类型的所有可能的图灵函数

haskell - 在 Haskell 中生成一个类型的所有可能的图灵函数

问题描述

我想在 Haskell 中暴力破解一些图灵机。这些图灵机具有以下类型的 Delta 函数：

type Delta state alphabetSymbol
   = (state -> alphabetSymbol -> (alphabetSymbol, Direction, state))

在哪里

data Direction
= L
| R
deriving (Eq, Show, Enum)

在我想暴力破解的具体示例中，我的状态和符号类型是以下枚举：

data State
= Q0
| Q1
| QF
deriving (Show, Eq, Enum)

data Symbol
= Zero
| One
| Blank
deriving (Show, Eq, Enum)

我想用这些总和类型有效地生成（几乎）所有可能的 Delta 函数。几乎，因为函数永远不会被调用QFas a state，所以我不需要担心QF输入。

我已经编写了一个基于指令生成它们的愚蠢的高级函数，但是它在列表中查找内容，这使得它非常低效。另外，我想把这个做得漂亮！

标签： haskellturing-machines

解决方案

我认为您应该将 [turing-machines] 标签添加到您的问题中。

图灵机的类型：

问题中涉及的类型系统可以做得更详细：

import qualified  Data.List   as  L
import qualified  Data.Map    as  M
import qualified  Data.Maybe  as  Mb
import qualified  Data.Tuple  as  T


type Delta state symbol direction
    = ( state -> symbol -> (state, symbol, direction) )


data State     = Q0 | Q1 | QF        deriving (Show, Eq, Enum, Ord, Bounded)

data Symbol    = Zero | One | Blank  deriving (Show, Eq, Enum, Ord, Bounded)

data Direction = L | R               deriving (Eq, Show, Enum, Ord, Bounded)

stateList     = [minBound .. maxBound] :: [State]
symbolList    = [minBound .. maxBound] :: [Symbol]
directionList = [minBound .. maxBound] :: [Direction]

type DeltaTable =
    M.Map  (State, Symbol)   (State, Symbol, Direction)

type DeltaFunc = Delta  State Symbol Direction

tmInpList :: [ (State, Symbol) ]
tmInpList = do 
              st <- filter  (/= QF)  stateList  -- cannot start from state QF
              sy <- symbolList
              return (st, sy)

tmInpListSize = length tmInpList

tmMapInpList :: M.Map Int (State, Symbol)
tmMapInpList = M.fromList $ zip  [ 0 .. (tmInpListSize-1) ]  tmInpList

tmOutList :: [ (State, Symbol, Direction) ]
tmOutList = do 
              st  <- stateList
              sy  <- symbolList
              dir <- directionList
              return (st, sy, dir)

tmOutListSize = length tmOutList

tmMapOutList :: M.Map Int (State, Symbol, Direction)
tmMapOutList = M.fromList $ zip  [ 0 .. (tmOutListSize-1) ]  tmOutList

上面的代码处理输入（状态、符号）对和输出（状态、符号、方向）三元组。它提供了所有可能的配对和三元组的列表，tmInpList以及tmOutList. 图灵转换表将对映射到三元组。

该代码还提供了辅助索引映射对象tmMapInpList和tmMapOutList，它们将整数等级映射到它们各自按字典顺序排列的列表中的对和三元组。使用整数索引的原因是，即使可以直接循环通过三元组，这也比下面提供的暴力代码慢了大约 10 倍，后者系统地使用整数索引。

我们有 2*3 = 6 个可能的输入对，因为输入不允许 QF 状态。我们在输出上有 3*3*2 = 18 个可能的三元组。因此，可能的转换表数量为 18^6 = 34,012,224。

索引和循环代码：

为了遍历所有可能的转换表，我们使用长度为 6 的整数列表，例如 [4,6,8,2,13,10]。它们从 [0,0,0,0,0,0] 变为 [17,17,17,17,17,17]。然后这些列表被映射到三元组列表。

这些短整数列表由表达式生成：

tmIndexList = sequence $ replicate 6  [ 0 .. 17 ]

生成所有 34,012,224 个可能的转换图的索引代码如下所示：

tmIndexList :: [[Int]]
tmIndexList = sequence $ replicate  tmInpListSize  [ 0 .. (tmOutListSize-1) ]
tmIndexListSize = length tmIndexList


deltaTableFromIndexes :: [Int] -> DeltaTable
deltaTableFromIndexes indexList =
    let outFromIndex = (\ix -> Mb.fromJust $ M.lookup ix tmMapOutList)
    in  M.fromList $ zip  tmInpList  (map  outFromIndex  indexList)


-- big list of map objects mapping (st, sy) to (st', sy', dir)
deltaTableList :: [DeltaTable]
deltaTableList = map deltaTableFromIndexes tmIndexList

-- big list of  *functions*  mapping  st sy  to  (st', sy', dir)
deltaFuncList :: [DeltaFunc]
deltaFuncList = let funcFromMap ma = (\st sy -> Mb.fromJust $ M.lookup (st,sy) ma)
                in  map funcFromMap deltaTableList

该deltaTableList变量是所有可能的地图对象的列表。地图对象的列表版本如下所示：

[((Q0,Zero),(QF,Blank,R)),((Q0,One),(QF,Blank,R)),((Q0,Blank),(QF,One,R)),((Q1,Zero),(QF,Blank,L)),((Q1,One),(Q0,Blank,L)),((Q1,Blank),(QF,Blank,L))]

问题文本提到功能而不是地图。但是，使用映射更实用，因为您可以从映射到函数，但不能从函数到映射。可以这么说，函数是不透明的。见deltaFuncList上述定义。

主程序：

为了在以下主程序中强制执行评估，我们在接近列表末尾的 34,000,000 处打印地图。

prettyPrintMap :: DeltaTable -> String
prettyPrintMap ma =
    let ptrls = M.toList ma
        fn = \(p,tr) -> (show p) ++ " -> " ++ (show tr) ++ " ; "
    in  (concatMap fn ptrls)


main = do
    putStrLn $ "  tmInpListSize   = "  ++  (show tmInpListSize)
    putStrLn $ "  tmOutListSize   = "  ++  (show tmOutListSize)
    putStrLn $ "  tmIndexListSize = "  ++  (show tmIndexListSize)

    -- force printing of one transition table close to the end of the list
    let ma34m = deltaTableList !! (34*1000*1000)
    putStrLn $ "Plain  ma34m = " ++ (show ma34m)
    putStrLn $ "Pretty ma34m = " ++ (prettyPrintMap ma34m)
    putStrLn $ " "

使用简短的性能指标执行：

$ ghc -O2 turing01.hs  -o turing01.x
$
$ time ./turing01.x +RTS -s -RTS

  tmInpListSize   = 6
  tmOutListSize   = 18
  tmIndexListSize = 34012224

Plain  ma34m = fromList [((Q0,Zero),(QF,Blank,R)),((Q0,One),(QF,Blank,R)),((Q0,Blank),(QF,One,R)),((Q1,Zero),(QF,Blank,L)),((Q1,One),(Q0,Blank,L)),((Q1,Blank),(QF,Blank,L))]
Pretty ma34m = (Q0,Zero) -> (QF,Blank,R) ; (Q0,One) -> (QF,Blank,R) ; (Q0,Blank) -> (QF,One,R) ; (Q1,Zero) -> (QF,Blank,L) ; (Q1,One) -> (Q0,Blank,L) ; (Q1,Blank) -> (QF,Blank,L) ; 

   5,873,144,856 bytes allocated in the heap
   3,516,995,416 bytes copied during GC
     886,616,408 bytes maximum residency (11 sample(s))
...

  %GC     time      76.6%  (76.6% elapsed)
  Productivity  23.4% of total user, 23.4% of total elapsed

real    0m3,692s
user    0m3,096s
sys     0m0,588s

因此，对于问题中提供的确切的图灵状态和字母集，蛮力技术证明是可行的。当然，添加更多状态和符号会很快导致执行时间的组合爆炸。

推荐阅读