Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 exptools; site ihnet.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!mhuxv!mhuxh!mhuxj!mhuxn!ihnp4!ihnet!eklhad
From: eklhad@ihnet.UUCP (K. A. Dahlke)
Newsgroups: net.math
Subject: How Did They Get 64403380965376?
Message-ID: <261@ihnet.UUCP>
Date: Sun, 21-Jul-85 11:00:57 EDT
Article-I.D.: ihnet.261
Posted: Sun Jul 21 11:00:57 1985
Date-Received: Mon, 22-Jul-85 08:40:10 EDT
Distribution: net
Organization: AT&T Bell Laboratories
Lines: 35

<  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