eklhad@ihnet.UUCP (K. A. Dahlke) (07/21/85)
< All hail the line eating bug > A recent issue of science news (Feb 85) described a 5 state turing machine with some very interesting properties. Although this machine (a busy beaver) is quite interesting, I shall dwell on another point. The author said that finding such a machine was difficult, since there are so very many turing machines, even if you are considering 5-state machines (relatively simple ones). Specifically, the author claims there are 64403380965376 5-state machines. I am confused, where did this number come from? By the definition of a turing machine, every state.input (10) produces an output.state.shift (20), or an output.halt (2). There are also 5 possible "initial" states, producing a combinatorics formula: 5 * (20+2)^10 = 132799613957120 (too high). Some of these machines must have been disqualified. I see two areas for concern: isomorphisms and connectivity. Two machines are isomorphic if the states (and transition matrix) of one machine can be relabeled, to produce the other. A machine is not connected if there are some states that can never be reached. It looks like a graph theory problem. Also, machines with multiple "halt" transitions may have been discarded. For each unique, connected 5-state machine, I can vary the output function as I please. Therefore, I divided the total by 2^10, to obtain the number of the author's base machines. Base machines = 62893926724. Based on these numbers, or any inside information, can anyone tell me what criteria were used to determine an acceptable 5-state machine, and how this number was calculated? Thanks. -- I never know what to put in these damn .signature files. Everybody expects me to be clever, or profound, or cute, or funny. I just can't take the pressure any more. They're out to get ... Doctor? ... Hey, where are you going? My session isn't over yet!!! Karl Dahlke ihnp4!ihnet!eklhad