I have an algorithm that is implemented by the following state table for a Turing machine:
𝑞1 | 𝑞2 | 𝑞3 | |
---|---|---|---|
0 | 0R 𝑞1 | 1L 𝑞3 | 0L 𝑞3 |
1 | 1R 𝑞1 | 0L 𝑞2 | 1L 𝑞3 |
_ | _L 𝑞2 | 1S 𝑞0 | _3 𝑞0 |
I want to determine the algorithm's complexity. To do that I think I should count the number of steps the Turing Machine makes before halting.
But I don't know the input on the tape.
How can I determine the complexity of this algorithm without knowing the input?
Assuming the start state is 𝑞1, the TM head will move to the right side of the input and then transition to state 𝑞2. Now realise that whatever happens after this point, the TM will never get back to state 𝑞1 again. Also, the only head-moves that can happen from this point onwards are 𝐿 (left), whether the state is 𝑞2 or 𝑞3, with one exception when the blank at the left side of the input is reached in state 𝑞2: then an 𝑆 (no move) can occur exactly once and then the state transitions to 𝑞0, which is an end-state (as there are no transitions defined for 𝑞0).
The head first moves to the extreme right and then back to the extreme left; the number of executed transitions is thus near 2𝑛 (to be precise: 2𝑛+2), where 𝑛 is the size of the input, and so we can say the complexity is O(𝑛).
If we analyse more closely, we can see that this algorithm takes a binary representation of an integer and increments it by one. It does so by flipping all right-sided 1 to 0 and the 0 that delimits that suffix (or if none is present: a blank) is flipped to a 1.
To test the TM a bit, you can use the implementation below:
createTuring({
transitions: [
{ state: "q1", read: "01", move: "R", nextState: "q1" },
{ state: "q1", read: "_", move: "L", nextState: "q2" },
{ state: "q2", read: "0", write: "1", move: "L", nextState: "q3" },
{ state: "q2", read: "1", write: "0", move: "L", nextState: "q2" },
{ state: "q2", read: "_", write: "1", nextState: "q0" },
{ state: "q3", read: "01", move: "L", nextState: "q3" },
{ state: "q3", read: "_", move: "R", nextState: "q0" },
],
initState: "q1",
tape: "11101101",
});
<script src="https://trincot.github.io/turing.js"></script>