Currently, I am trying to work on a Turing Machine. It should take in a sequence k, x1, x2, . . . , xn where k is a positive integer and for each i, xi is a nonnegative integer as input. All the numbers will be encoded in the form of a^k b a^x1 b a^x2 b ..... b a^xn.
For output, it should output the value of the k-th element.
For example: If my input is aaababaaaaabaa(k = 3, 1st element = 1, 2nd element = 5, 3rd element = 2)
In this case, the Turing Machine should display the output as aa(2). The problem currently I am facing is I have no idea how to keep track of the number k since there is no counter/memory to store the value k. Also, I have no idea how to output the value even if I've keep tracked of the k-th element
I had try to use the marking symbol technique where for each read of a from k, it will write it as A and go right to find b. If b is found, then write it as B and go back to find A. In this case, I can keep track of each A and B (my idea is like cancelling each a with each b). But at the end, when there are no more A and B, I have no idea how to go to the k-th element and output the value.
Hope someone can help me with this.
p/s: I am using a Tuatara Simulator
Thank you.
You can keep track of the decreasing number of 𝑘 by mapping each a that belongs to the encoding of 𝑘 with a b. The idea to mark the characters that belong to such a pair is a good one. Once you have no more (unmarked) a left over, you can start to delete characters up until (and including) the first unmarked b. The a that follow should stay. Finally delete any characters that follow that series of a.
This approach would actually select the k+1th number, so just delete the first a without mapping it to a b to compensate for that.
You mentioned in comments that you are using a one-sided Turing Machine, where it is infinite to the right, but has a start at the left, where also the head starts. As you indicated that the expected output should be left-aligned at the start of the tape, you'll need some extra states and transitions to "move" the found sequence of a to the left. You can do this in different ways. One is to delete the rightmost a and write one at the left side of the sequence. Repeat this until you arrive at the start of the tape, which we could mark with a letter "A".
I would also wipe out the a that belong to 𝑘 instead of marking them with an uppercase, as in the end you'll want to delete or replace those anyway.
Here is a possible transition table:
| state | read | write | move head | next state |
|---|---|---|---|---|
| start | a | A | right | get |
| start | b or _ | right | reject | |
| get | a | _ | right | findb |
| get | B | _ | right | wipe |
| get | b | _ | right | keep |
| findb | a or B | right | findb | |
| findb | b | B | left | rewind |
| findb | _ | left | reject | |
| rewind | a or B | left | rewind | |
| rewind | _ | right | get | |
| wipe | a or B | _ | right | wipe |
| wipe | b | _ | right | keep |
| wipe | _ | left | reject | |
| keep | a | right | keep | |
| keep | _ | left | pickup | |
| keep | b | _ | right | trim |
| trim | a or b | _ | right | trim |
| trim | _ | left | pickup | |
| pickup | a | _ | left | roll |
| pickup | _ | left | pickup | |
| pickup | A | _ | accept | |
| roll | a | left | roll | |
| roll | _ | a | right | right |
| right | a | right | right | |
| right | _ | left | pickup | |
| roll | A | a | accept |
The initial state is "start" and a blank is represented by "_". If the input has a solution, the final state will be "accept".
Here is a runnable implementation with that transition table:
createTuring({
transitions: [
{ state: "start", read: "a", write: "A", move: "R", nextState: "get" },
{ state: "start", read: "b_", move: "R", nextState: "reject" },
{ state: "get", read: "a", write: "_", move: "R", nextState: "findb" },
{ state: "get", read: "B", write: "_", move: "R", nextState: "wipe" },
{ state: "get", read: "b", write: "_", move: "R", nextState: "keep" },
{ state: "findb", read: "aB", move: "R", nextState: "findb" },
{ state: "findb", read: "b", write: "B", move: "L", nextState: "rewind" },
{ state: "findb", read: "_", move: "L", nextState: "reject" },
{ state: "rewind", read: "aB", move: "L", nextState: "rewind" },
{ state: "rewind", read: "_", move: "R", nextState: "get" },
{ state: "wipe", read: "aB", write: "_", move: "R", nextState: "wipe" },
{ state: "wipe", read: "b", write: "_", move: "R", nextState: "keep" },
{ state: "wipe", read: "_", move: "L", nextState: "reject" },
{ state: "keep", read: "a", move: "R", nextState: "keep" },
{ state: "keep", read: "_", move: "L", nextState: "pickup" },
{ state: "keep", read: "b", write: "_", move: "R", nextState: "trim" },
{ state: "trim", read: "ab", write: "_", move: "R", nextState: "trim" },
{ state: "trim", read: "_", move: "L", nextState: "pickup" },
{ state: "pickup", read: "a", write: "_", move: "L", nextState: "roll" },
{ state: "pickup", read: "_", move: "L", nextState: "pickup" },
{ state: "pickup", read: "A", write: "_", nextState: "accept" },
{ state: "roll", read: "a", move: "L", nextState: "roll" },
{ state: "roll", read: "_", write: "a", move: "R", nextState: "right" },
{ state: "right", read: "a", move: "R", nextState: "right" },
{ state: "right", read: "_", move: "L", nextState: "pickup" },
{ state: "roll", read: "A", write: "a", nextState: "accept" },
],
initState: "start",
tape: "aaababaaaaabaa"
});<script src="https://trincot.github.io/turing.js"></script>