Turing Machine - Finding k-th element and move it to the front of the tape

I am trying to solve the following Turing machine challenge:

The number choice function

The number choice function is defined as follows.

INPUT: a sequence 𝑘, 𝑥₁, 𝑥₂,..., 𝑥_𝑛 where

• 𝑘 is a positive integer.

• For each 𝑖, 𝑥_𝑖 is a nonnegative integer.

• All these numbers are encoded in unary using repetition of the letter a, with the letter b used as a separator (in effect, playing the role of the commas). So the input sequence 𝑘, 𝑥₁, 𝑥₂,..., 𝑥_𝑛 is encoded as the string

        a𝑘ba𝑥1ba𝑥2b....a𝑥𝑛

OUTPUT: 𝑥_𝑘, i.e. the 𝑘-th of the 𝑥 numbers.

• This also is encoded in unary in the same way, but without any b at the end. So the output 𝑥_𝑘 is encoded as the string a𝑥𝑘.
• Recall the definition of the output of a Turing machine from Lecture 18 slide 28 (or Course Notes §18.8 p. 223). Once the machine enters the Accept state, it does not matter what comes after the leftmost blank cell; those later cells are not considered to be part of the output string.

Some examples inputs and outputs:

input sequence	input encoded as string	output number	output encoded as string
3,1,5,2	aaababaaaaabaa	2	aa
2,4,7,0,3	aabaaaabaaaaaaabbaaa	7	aaaaaaa
1,0,1	abba	0	ε [first tape cell must be empty]
1,3,2,0	abaaabaab	3	aaa
3,3,2,0	aaabaaabaab	0	ε [first tape cell must be empty]
0,1,5,2	babaaaaabaa	undefined	crash: invalid input, k = 0
4,1,5,2	aaaababaaaaabaa	undefined	crash: invalid input, k > n

Notes:

• Any input string that is not of the specified form should be rejected, by crashing. Examples of situations that must lead to a crash include: 𝑘 = 0; 𝑘 > 𝑛.
• You can, and should, have extra letters in your tape alphabet that are not in the input alphabet {a,b}

Question Image

I managed to cancel each initial a with each b by using the marking symbol technique, where for each read of a from 𝑘, 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.

But at the end, when there are no more A and B, I have no idea how to go to the 𝑘-th element and output the value, which would mean I had to somehow move that element to the front of the tape.

How can I achieve that?

p/s: I am using a Tuatara Simulator, which has a tape that extends infinitely only to the right. The head starts at the extreme left side of the tape.

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+1^th 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:

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>