Turing Machine - Finding k-th element among unary encoded numbers

I am trying to solve the following Turing machine challenge:

The number selection function

The number selection function is defined as follows.

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

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

𝑘 is a positive 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^𝑥₂...a^𝑥_𝑛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. 227). Once the machine enters the Accept state, it does not matter what comes after the lefmost blank cell; those later cells are not considered to be part of the output string.

Some example inputs and outputs:

input sequence input encoded as string output number output encoded as string

1,5,2,3 abaaaaabaabaaa 2 aa

4,7,0,3,2 aaaabaaaaaaabbaaabaa 7 aaaaaaa

0,1,1 baba 0 ε [first tape cell must be empty]

3,2,0,1 aaabaabba 3 aaa

3,2,0,3 aaabaabbaaa 0 ε [first tape cell must be empty]

1,5,2,0 abaaaaabaab undefined crash: invalid input, 𝑘 = 0

1,5,2,4 abaaaaabaabaaaa undefined crash: invalid input, 𝑘 > 𝑛

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

input sequence	input encoded as string	output number	output encoded as string
1,5,2,3	`abaaaaabaabaaa`	2	`aa`
4,7,0,3,2	`aaaabaaaaaaabbaaabaa`	7	`aaaaaaa`
0,1,1	`baba`	0	ε [first tape cell must be empty]
3,2,0,1	`aaabaabba`	3	`aaa`
3,2,0,3	`aaabaabbaaa`	0	ε [first tape cell must be empty]
1,5,2,0	`abaaaaabaab`	undefined	crash: invalid input, 𝑘 = 0
1,5,2,4	`abaaaaabaabaaaa`	undefined	crash: invalid input, 𝑘 > 𝑛

So for this problem my approach is:

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

Here is my code:

createTuring({
    transitions: [
        // First, move to the end of the tape
        { state: "start",  read: "a",               move: "R", nextState: "start" },
        { state: "start",  read: "b",               move: "R", nextState: "start"  },
        { state: "start",  read: "_",               move: "L", nextState: "init"   },
        
        // Begin the algorithm from the end
        { state: "init",   read: "a",   write: "A", move: "L", nextState: "get"    },
        { state: "init",   read: "b",              move: "L", nextState: "reject" },
        { state: "init",   read: "_",              move: "L", nextState: "reject" },
        
        { state: "get",    read: "a",   write: "_", move: "L", nextState: "findb"  },
        { state: "get",    read: "B",   write: "_", move: "L", nextState: "wipe"   },
        { state: "get",    read: "b",   write: "_", move: "L", nextState: "keep"   },
        
        { state: "findb",  read: "aB",              move: "L", nextState: "findb"  },
        { state: "findb",  read: "b",   write: "B", move: "R", nextState: "rewind" },
        { state: "findb",  read: "_",               move: "R", nextState: "reject" },
        
        { state: "rewind", read: "aB",              move: "R", nextState: "rewind" },
        { state: "rewind", read: "_",               move: "L", nextState: "get"    },
        
        { state: "wipe",   read: "aB",  write: "_", move: "L", nextState: "wipe"   },
        { state: "wipe",   read: "b",   write: "_", move: "L", nextState: "keep"   },
        { state: "wipe",   read: "_",               move: "R", nextState: "reject" },
        
        { state: "keep",   read: "a",               move: "L", nextState: "keep"   },
        { state: "keep",   read: "_",               move: "R", nextState: "pickup" },
        { state: "keep",   read: "b",   write: "_", move: "L", nextState: "trim"   },
        
        { state: "trim",   read: "ab",  write: "_", move: "L", nextState: "trim"   },
        { state: "trim",   read: "_",               move: "R", nextState: "pickup" },
        
        { state: "pickup", read: "a",   write: "_", move: "R", nextState: "roll"   },
        { state: "pickup", read: "_",               move: "R", nextState: "pickup" },
        { state: "pickup", read: "A",   write: "_",            nextState: "accept" },
        
        { state: "roll",   read: "a",               move: "R", nextState: "roll"   },
        { state: "roll",   read: "_",   write: "a", move: "L", nextState: "left"   },
        { state: "roll",   read: "A",   write: "a",            nextState: "accept" },
        
        { state: "left",   read: "a",               move: "L", nextState: "left"   },
        { state: "left",   read: "_",               move: "R", nextState: "pickup" },
    ],
    initState: "start",
    tape: "abaaaaabaabaaa"
});

<script src="https://trincot.github.io/turing.js"></script>

The problem is I have no idea how can I take the order from left to right.

Ex:

Input sequence: 1,5,2,3

My current code will take the 3rd position from right to left, but I want it take 3rd position from left to right.

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.

Solution

There are some particularities of the Tuatara simulator to take into account:

The tape has a leftmost cell, and any attempt to move the head to the left of it is an invalid operation (the simulator displays a popup message). There is no way to know you are on the leftmost cell, so you must keep track of this so not to make that invalid operation.
A transition on this machine can either write a symbol or move the head, but it cannot do both. This means that you'll often have to introduce extra states and transitions compared to Turing machines that can do both operations in one transition.
An accept state is not enough. For the input to be considered accepted, the head must also be put at the leftmost position.
The output must be written at the very left side of the tape.
The first blank denotes the end of the output, and all symbols to the right of it are ignored.

To tackle the first point I would suggest to take a pragmatic approach and first shift all input symbols one position to the right (through transitions), inserting a special symbol "s" at the leftmost position. This way you know during the rest of the execution whether you are at the left edge of the tape or not. The very last action can consist of replacing that symbol again.

Suggested algorithm

Insert the symbol "s" at the left edge of the tape, shifting all non-blank symbols one position to the right as you traverse the contents from left to right
Don't bother shifting the very last "a" that belongs to K, just drop it: this makes K a zero-based index instead of the 1-based position, which is OK for this algorithm.
Now that the head is at the right side, start the following loop, for as long as the rightmost symbol is not a "b" (which would mean that K has reduced to 0)
1. Replace the rightmost "a" with a blank: this decrements K.
2. Walk to the left up to the leftmost "a"
3. Replace all consecutive "a" (from where the head is) with "z" to indicate you wipe out this input number
4. Walk back to the very right of the input and repeat these steps until the rightmost character is a "b"
Walk to the leftmost "a" which is part of the input number we want to output
Move the consecutive "a" (from where the head is) to the left side of the tape (but not touching the "s" symbol). This involves a zig-zag loop where each such "a" is taken away and written more to the left.
Now we need to remove the "s", which means we take the rightmost "a" that is part of the consecutive block that was moved in the previous step, replace it with a blank (to denote the end of the input) and finally replace the "s" at the left with that "a".

Here is an implementation with the JavaScript implementation you used in your question. To stay in line with the Tuatara simulator, it has no transitions that perform both a write and a move operation:

createTuring({
    transitions: [
        // First, insert a marker at the start of the tape, moving the existing content one position
        //   to the right, because moving the head left when on the first spot
        //   will make the machine crash on the Tuatara simulator:
        { state: "start",     read: "a",   write: "s", nextState: "moveA"    },
        { state: "start",     read: "b",   write: "s", nextState: "moveB"    },
        { state: "moveA",     read: "sb",  move:  "R", nextState: "writeA"   },
        { state: "writeA",    read: "a",   move:  "R", nextState: "writeA"   },
        { state: "writeA",    read: "b",   write: "a", nextState: "moveB"    },
        { state: "writeA",    read: "_",   move:  "L", nextState: "decrK"    },
        { state: "moveB",     read: "sa",  move:  "R", nextState: "writeB"   },
        { state: "writeB",    read: "b",   move:  "R", nextState: "writeB"   },
        { state: "writeB",    read: "a",   write: "b", nextState: "moveA"    },
        // Now all is shifted, and K decreased to make it a 0-based index, try to decrease K
        { state: "decrK",     read: "a",   write: "_", nextState: "find"     },
        // Or if K was 0, identify the first non-wiped X
        { state: "decrK",     read: "b",   move:  "L", nextState: "find2"    },
        // Look for start of non-wiped X
        { state: "find",      read: "_ab", move:  "L", nextState: "find"     },
        { state: "find",      read: "zs",  move:  "R", nextState: "wipeA"    },
        // First X found. Now wipe it
        { state: "wipeA",     read: "a",   write: "z", nextState: "find"     },
        { state: "wipeA",     read: "b",   write: "z", nextState: "next"     },
        // Find K again in order to decrease it
        { state: "next",      read: "zab", move:  "R", nextState: "next"     },
        { state: "next",      read: "_",   move:  "L", nextState: "decrK"    },
        // Find first non-wiped X in order to move it to the start of the tape
        { state: "find2",     read: "ab",  move:  "L", nextState: "find2"    },
        { state: "find2",     read: "zs",  move:  "R", nextState: "readA"    },
        // Found first X: move its first A to the start of the tape
        { state: "readA",     read: "a",   write: "z", nextState: "alignA"   },
        { state: "readA",     read: "b",   move:  "L", nextState: "empty"    },
        { state: "alignA",    read: "z",   move:  "L", nextState: "alignA"   },
        { state: "alignA",    read: "sa",  move:  "R", nextState: "finalA"   },
        { state: "finalA",    read: "z",   write: "a", nextState: "right"    },
        // Moved one A, now repeat for more As
        { state: "right",     read: "a",   move:  "R", nextState: "fetch"    },
        { state: "fetch",     read: "z",   move:  "R", nextState: "fetch"    },
        { state: "fetch",     read: "a",   write: "z", nextState: "alignA"   },
        { state: "fetch",     read: "b",   move:  "L", nextState: "findlast" },
        // All A moved. Now we need to move the rightmost of them to the first spot
        { state: "findlast",  read: "z",   move:  "L", nextState: "findlast" },
        { state: "findlast",  read: "a",   write: "_", nextState: "tostart"  },
        { state: "tostart",   read: "_a",  move:  "L", nextState: "tostart"  },
        { state: "tostart",   read: "s",   write: "a", nextState: "accept"   },
        // Deal with boundary case where output must be empty
        { state: "empty",     read: "z",   move:  "L", nextState: "empty"    },
        { state: "empty",     read: "s",   write: "_", nextState: "accept"   },
    ],
    initState: "start",
    tape: "abaaaaabaabaaa"
});

<script src="https://trincot.github.io/turing.js"></script>

When the input is invalid, then the above implementation will just stop at some state that is not the "accept" state.

This should be straightforward to map to the Tuatara simulator (but tedious as you have to design it with a drag/drop user interface).