Testing a Turing Machine Simulation Program

Question

I am trying to come up with large Test Cases for a Turing Machine Simulator program in Java.

The program reads data from an input file and runs the simulation based on a testcase string and a list of Turing Machine rules. After executing the rules below the program will print whether or not the string is accepted, rejected or does not halt in a given number of steps.

The program is basically simulation of manually walking through a Turing State Machine on paper, given some input string.

I found that testing this program is difficult. The program works great for all basic Turing Machines, and relatively small test cases. I would like to test this program given a very large test string (~30 characters), 5000 steps, and some large number or rules and states.

I was wondering if someone can help me come up with a good test case for this?

Sample Test Case

7 15 //number of states and number of rules
0 0 3 B R //[current state, transition character, destination state, value to write, direction to move]
0 B 2 B R
0 x 2 x R
3 x 3 x R
3 B 1 B R
3 0 6 x R
6 x 6 x R
6 0 4 0 R
6 B 5 B L
4 x 4 x R
4 B 2 B R
4 0 6 x R
5 0 5 0 L
5 x 5 x L
5 B 3 B R
3 15 //number of testcases and number of steps to come to a halt
00
000
000000

Many thanks in advance

templatetypedef templatetypedef · Accepted Answer · 2013-02-24T18:57:39

If you're looking for test cases to stress-test your implementation, you might want to look at the busy beaver Turing machines, which are Turing machines with a specified number of states and tape symbols that are known to run for the longest possible time before terminating. We know exact bounds on how long it takes for those machines to finish running, so you should be able to both test your simulator on TMs that are known to use a lot of time and space and confirm that your step counter works correctly.

Hope this helps!

Testing a Turing Machine Simulation Program

1 Answers