How can I simulate a turing machine?

Question

I don't quite understand the whole idea of a turing machine thing.

I am currently tasked with making a busy beaver turing machine. But the thing I don't really get is it simulates input. So what kind of input do I simulate? For example, it's asking me how many 1s the 3 states busy beaver machines writes on tape? I'm sure I need to write a turing machine, but once I have it, what do I do with it?

What string should I simulate it with?

Answer 1

For the busy beaver scenario, it is usually assumed that there is no special input, i.e. the tape of the Turing Machine is initially empty. Of course, during its runtime, the busy beaver may write to the tape and later read what it has written.

So you do have to simulate the tape. Since it's supposed to be infinite at both ends, I'd suggest to implement it by subclassing ArrayList and overwriting the get() and set() methods to map positive indices to even elements and negative indices to odd elements (and also to automatically increase the size by repeatedly calling add(null) when there is an access to an index outside the current size of the list).

Answer 2

Your first step would be get a better understanding of 'the whole idea of turing machine thing'. You could try to read up on it:

• wikipedia here (simple) and here
• another explanation