C (gcc), Score 622410 442766 states
Now ported from bash to C so it's much faster! (The program constructs all 20,000 Turing machines on TIO in about 10 seconds total.)
Note that this version of the program always computes all 20,000 Turing machines (saving them in 20,000 separate files). This is handy if you download the program and run it on your own computer. (TIO appears to delete all files as soon as the program halts, so the 20,000 files aren't very useful in that environment.)
It also displays one of the Turing machines on stdout (as determined by an argument you pass to it). This is practical for TIO.
Thanks to Surculose Sputum for pointing out that state t+3 in the original version was superfluous. Taking it out reduced the total number of states considerably!
Other changes: Reduced the base cases from 6 to 4. Fixed a few typos in the documentation, and improved the explanation a bit.
This program is based on a recursive construction: the idea is to construct an \$n\$-step Turing machine by taking a previously constructed \$\frac{n}{2}\$-step Turing machine and running it twice (except that this is adjusted a bit to take overhead into account).
I like this construction because it's easy to understand.
The program computes the Turing machines for 1 up to 20000, and it writes each Turing machine to a separate file.
It also accepts an argument \$n,\$ and displays the \$n\$-step Turing machine that was constructed on stdout (the default value for \$n\$ is 20000).
The score is correct for the challenge even if you request one of the smaller Turing machines, since, no matter what you pass as an argument, it always computes all 20,000 Turing machines and prints the correct codegolf challenge score for all 20,000 machines total.
If you run this on your own computer, run it in a directory by itself, because it will create files T1, T2, T3, ..., T20000 in the directory it's run in (one for each Turing machine).
/**********
INTRODUCTION
For each n from 1 to 20000, this program computes a Turing
machine Tn which takes exactly n steps when it runs.
The program writes all the computed Turing machines to
files T1, T2, T3, ..., T20000.
The total number of states for all 20000 machines is then
displayed. (This is the score for the codegolf challenge.)
Also, one argument n is accepted on the command line; if provided,
it must be a number between 1 and 20000. Turing machine Tn is
displayed on stdout.
If no argument is provided, the default is 20000.
Note that all 20000 machines are always computed and written
to the files on disk, but only the one you specify is written
to stdout.
Total time taken is about 10 seconds on TIO.
**********/
/**************
HOW TO COMPILE AND RUN
Save this file as tm.c, and compile it with the command
gcc -O3 -o tm tm.c
or, if you prefer,
gcc -O3 -Wall -Werror -W -o tm tm.c
Run it with a command like
./tm
or
./tm 50
This will display the Turing machine requested (T20000 or T50, in
the two examples above).
But you can look at all 20000 Turing machines in any case, since
they're all saved in files T1, T2, T3, ..., T20000.
(On TIO, the system will delete the saved files as soon as the
program finishes running, so they're not very useful in that
environment.)
**************/
/***************
FUNDAMENTAL IDEA
The idea is to compute a Turing machine which takes n steps to
run, by doing something as close as possible to the following:
Recursively take a machine that takes about n/2 steps to halt,
and run it twice. (The base case for the recursion will be
n <= 4.)
This needs to be adjusted slightly because there are 3 steps
needed for overhead, so we need to use a machine that takes
(n-3)/2 steps to halt, instead of n/2 steps.
Also, if n is even, this leaves us one step short, so we
need to add an extra step in that case.
Since the challenge is to compute a machine for each n up to
20,000, there's no need to implement this using recursion in
the code. Instead we just run through a loop, computing a
Turing machine for each n in turn. But each computation
uses the previous results, just as the recursion suggests.
***************/
/***************
PROPERTIES OF THE CONSTRUCTED TURING MACHINES
These Turing machines never move to the left of position 0
(the starting position of the tape head).
If the all the cells from the starting position to the right
are initially 0, then Tn will take exactly n steps to run.
Each Turing machine leaves everything exactly as it found it
(tape cell data and tape head position).
Output format:
The program will write Turing machine Tn to a file called Tn
(where n is replaced by the actual number).
During execution, the Turing machine Tn is divided into 3 separate pieces:
The array element stateCountArray[n] holds the number of states.
The file An holds tuples in the form movement newval newstate for when
the tape head is looking at a 0.
The file Bn holds tuples in the form movement newval newstate for when
the tape head is looking at a 1.
An and Bn have one tuple for each state, in order from
state 1 to the number of states.
The eventual machine Tn will consist of stateCountArray[n], An, and Bn, in that order.
***************/
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#define MAXn (20000)
int stateCountArray[MAXn + 1];
char filenameTemplate[] = "X99999";
int score = 0;
void openTupleFiles(int n, FILE **file0, FILE **file, char *fileMode);
void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1);
void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file);
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.
**********/
void basis(void);
void invalidArgument(void);
int getNumericalArgument(int argc, char **argv);
void openTupleFiles(int n, FILE **file0, FILE **file1, char *fileMode)
/**********
Given n, opens the two files An and Bn, and returns them in the file
descriptors file1 and file2. The two files are opened in the indicated
mode: "r", "w", ....
**********/
{
sprintf(filenameTemplate, "A%d", n);
*file0 = fopen(filenameTemplate, fileMode);
*filenameTemplate = 'B';
*file1 = fopen(filenameTemplate, fileMode);
}
void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1)
/**********
Used by the function basis.
Sets up stateCountArray[n], An, and Bn as specified,
and updates score.
**********/
{
FILE *theFile;
stateCountArray[n] = numberOfStates;
sprintf(filenameTemplate, "A%d", n);
theFile = fopen(filenameTemplate, "w");
fputs(tuplesFor0, theFile);
fclose(theFile);
sprintf(filenameTemplate, "B%d", n);
theFile = fopen(filenameTemplate, "w");
fputs(tuplesFor1, theFile);
fclose(theFile);
score += numberOfStates;
} // createOnePrecomputedTuringMachine
void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file)
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.
oldFile should already be open for reading, and file should be open for writing.
Reads tuples from oldFile, writes tuples to file.
All states are shifted up by 1.
Each halting state is changed to a tuple which moves left and changes the state
to firstUnusedState.
**********/
{
char movement;
int newValue;
int newState;
while (3 == fscanf(oldFile, "%c%d%d%*c", &movement, &newValue, &newState))
{
if ('H' == movement)
{
movement = 'L';
newState = firstUnusedState;
}
else
newState++;
fprintf(file, "%c %d %d\n", movement, newValue, newState);
} // while
} // void adjustStates
void basis(void)
/**********
This handles values of n from 1 through 4, which form the basis of the recursion.
These Turing machines are precomputed.
**********/
{
createOnePrecomputedTuringMachine(1, 1, "H 0 1\n", "H 0 1\n");
createOnePrecomputedTuringMachine(2, 1, "S 1 1\n", "H 0 1\n");
createOnePrecomputedTuringMachine(3, 2, "S 1 1\nH 0 1\n", "S 1 2\nH 0 1\n");
createOnePrecomputedTuringMachine(4, 2, "S 1 1\nS 1 2\n", "S 0 2\nH 0 1\n");
} // basis
void invalidArgument(void)
{
printf("Usage: tm\n or: tm n\nwhere n is a number between 1 and 20000\n(default is 20000).\n");
exit(1);
}
int getNumericalArgument(int argc, char **argv)
{
char * arg;
char *p;
int k = 0;
if (argc < 2)
return 20000;
if (argc > 2)
invalidArgument();
arg = argv[1];
if (0 == *arg)
return 20000;
for (p = arg; *p; p++)
{
if ((*p < '0') || ('9' < *p))
invalidArgument();
k = 10 * k + *p - '0';
if (k > 20000)
invalidArgument();
}
return k;
}
#define BUFFERSIZE (4096)
int main(int argc, char **argv)
{
int n;
int m;
FILE *An;
FILE *Bn;
int t;
FILE *Am;
FILE *Bm;
FILE *TuringMachineFile;
char byteArray[BUFFERSIZE];
int numberOfBytesRead;
int argument;
if (argc > 2)
invalidArgument();
argument = getNumericalArgument(argc, argv);
// For each values of n, we compute stateCountArray[n] and the two files An and Bn.
// First take care of the basis, n = 1 through 4.
basis();
// Now start the main loop for n = 5 and up:
for (n = 5; n <= MAXn; n++)
{
// We'll go through 2 runs of the machine Tm that we
// computed earlier, where m = floor((n-3)/2).
// There are 3 steps of overhead, and we add in one
// extra step if n happens to be even, because in that
// case, 2 * floor((n-3)/2) + 3 is n-1, not n.
// This will get us to exactly n steps.
m = (n - 3)/2;
// Open files An and Bn for writing.
openTupleFiles(n, &An, &Bn, "w");
// Go through two runs of machine Tm.
// The cell at position 0 will keeep track of which run
// we're on (0 for the first run, 1 for the second).
// At the beginning, position 0 holds a 0, so we
// move right to position 1 and go to state 2.
fputs("R 0 2\n", An);
// For even n, at the end of the entire run of Tn, we'll
// find ourselves back in state 1 at position 0, but the
// contents of that cell will be 0, and we'll halt.
// (For odd n, the machine will halt without going back
// to state 1.)
fputs("H 0 1\n", Bn);
// Compute the number of states in the new machine Tn.
// It's two more than the number if states in Tm.
t = stateCountArray[m] + 2;
// Open files Am and Bm for reading.
openTupleFiles(m, &Am, &Bm, "r");
// The two calls below to the function adjustStates copy machine Tm
// into the Turing machine that we're building, with the following
// modifications:
// - Use states 2 through t+1 instead of 1 through t.
// - Halt tuples (H) get altered to tuples that don't halt
// but instead move left (L) and change to state t+2.
adjustStates(t, Am, An);
fclose(Am);
adjustStates(t, Bm, Bn);
fclose(Bm);
// Since we're in state 2 at position 1, we're all set to run
// the altered copy of Tm, so that happens next.
// After running the altered copy of Tm, we're back at position 0,
// since the original Tm would have left us at position 1, but the
// altered version changed every H to an L, causing the tape head
// to move left one position, to position 0.
// If the tape head is looking at 0 in position 0,
// we just finished the first of the two runs of Tm.
// In that case, write a 1 to position 0 to indicate
// that we're on the second run now.
// Move right to position 1 and change to state 2.
// That will start the second run of Tm.
fputs("R 1 2\n", An);
fclose(An);
// If the tape head is looking at a 1 in position 0,
// we just finished our second run of Tm. We're ready
// to halt, except that if n is even, we need to add
// one extra step.
if (n % 2)
{ // n is odd, so halt.
fputs("H 0 1\n", Bn);
}
else
{ // n is even, so change to state 1 (which
// will take the extra step we need).
// State 1 will then halt because it's
// looking at a 1.
fputs("S 1 1\n", Bn);
}
fclose(Bn);
// Store the number of states for Tn in stateCountArray,
// and update the score..
stateCountArray[n] = t;
score += t;
} // for n
// Print the codegolf challenge score (the total number of
// states in all 20000 Turing machines).
printf("Score (up to 20000) = %d\n\n", score);
// Write each Turing machine Tn to the file called Tn (where
// n is the actual number).
// First write stateCountArray[n], then copy file An, and
// after that copy file Bn.
// Also delete the files An and Bn.
for (n = 1; n <= MAXn; n++)
{
openTupleFiles(n, &An, &Bn, "r");
sprintf(filenameTemplate, "T%d", n);
TuringMachineFile = fopen(filenameTemplate, "w");
fprintf(TuringMachineFile, "%d\n", stateCountArray[n]);
numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, An);
fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
fclose(An);
numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, Bn);
fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
fclose(Bn);
fclose(TuringMachineFile);
*filenameTemplate = 'A';
unlink(filenameTemplate);
*filenameTemplate = 'B';
unlink(filenameTemplate);
} // for n
// Finally print the requested Turing machine to stdout.
(void) printf("Turing machine which halts after exactly %d steps:\n", argument);
sprintf(filenameTemplate, "T%d", argument);
TuringMachineFile = fopen(filenameTemplate, "r");
numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, TuringMachineFile);
fwrite(byteArray, sizeof(char), numberOfBytesRead, stdout);
fclose(TuringMachineFile);
exit(0);
} // main
Try it online!
