我想在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 函数。几乎，因为该函数永远不会以QF作为state调用，所以我不需要担心输入中的QF。
我已经编写了一个愚蠢的高级函数，它根据指令生成它们，但它在列表中查找内容，这使得它的效率非常低。另外，我想做得很漂亮！
我认为你应该在你的问题中添加[图灵机]标签。
图灵机的类型：
问题中涉及的类型系统可以更详细地说明：
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,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
因此，事实证明，蛮力技术对于问题中提供的图灵状态和字母表的确切集合是可行的。当然，添加更多的状态和符号会很快导致执行时间的组合爆炸。