[math-fun] Half forgotten AILab flashback
2 Oct
2016
2 Oct
'16
1:13 p.m.
Sometime ~ 1966?, Bill Henneman asked me to search for a counterexample to a conjecture about finite state (Moore) machines. It said something like a machine that accepts the star of a finite set has only cyclic subgroups in its state vector semigroup. Can someone render this coherent? It may have been for Minsky's Finite and Infinite Machines book. I remember representing the state vectors as blocks of indexed PUSH instructions, so you could multiply them by aiming one at the other and executing it, one instruction per state. Oh, that's right, data execution is now illegal. Anyway, I failed to find a counterexample, but I think Henneman constructed one. Why unmentioned in HAKMEM? --rwg
3337
Age (days ago)
3337
Last active (days ago)
0 comments
1 participants
participants (1)
-
Bill Gosper