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?

I believe that some readers are not interested to make the effort to understand your problem and write an answer, because of your never voted for anyone, never accepted any answer to one of your questions... — KLE, Oct 07 '09 at 08:41
I also think that people will post an answer if they understand you actually did try to solve the issue before posting here. This sounds a lot like "hey please solve my homework for me"... — reef, Oct 07 '09 at 08:47
Come on I have read and know that it's a powerful machine that can prove undecidability of number computation. But there is no example of how machine works?Anyway,I'm new here and don't know that I should accept people's answer.Forgive me.:)Thanks for that. — gingergeek, Oct 07 '09 at 08:55
working through a problem and reading about a problem is two way different concepts. if you work through it, post some code and ask intelligible questions people here will respect you a bit more and spend more time analyzing and answering your questions. — Nico, Oct 07 '09 at 09:03

score 7 · Answer 1 · edited May 23 '17 at 10:27

7

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

edited May 23 '17 at 10:27

Community

1
1

answered Oct 07 '09 at 08:47

akf

38,619
8
86
96

score 2 · Accepted Answer · answered Oct 07 '09 at 08:47

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).

Ahem ... call `ensureCapacity(number)` instead of `add(null)` — Aaron Digulla, Oct 07 '09 at 08:55
Doesn't work - it only grows the underlying array, but does not adjust the size field. — Michael Borgwardt, Oct 07 '09 at 10:09

How can I simulate a turing machine?

2 Answers2