Turing machines form a computational model and can implement any algorithm that can be written in Java, Javascript, C, Cobol, Rust, etc. All the algorithm you mention can then be implemented on a single-tape Turing machine. The resulting Turing machine is cumbersome.
Let us consider the example of Dijkstra's algorithm. The input is a weighted graph and is represented as a string on the Turing machine tape. For instance the string
#0-1:5#0-2:7#1-2:1
represents the graph with three nodes 0, 1, 2 and the edges 0->1 of weight 5, 0->2 of weight 7 and 1->2 of weight 1.
The inner states correspond to positions in your program. But contrary to a program in Java, etc., the program here is highly detailed! For instance, for adding two numbers written on the tape, you can mark each number with a mark - let say x for the first number, and y for the second number. You will also mark - by let say r - the place in the tape where the result should be written. You have to mark also the current digits that are considered by the addition algorithm. The tape looks like:
.....$143$.........$42$.......$000000$....
x y r
The addition algorithm will then move its head back and forth between the two numbers x and y and write each digit of the result in the zone marked by r.
Each part of Dijkstra's algorithm needs to be implemented in the same spirit:
- allocating memory to store the array of distances d
- checking whether the queue is empty
- computing the minimum of the current queue
- computing d[u] + weight(u, v)
- checking whether d[u] + weight(u, v) < d[v]
- update d[v]
Storing d[u] requires to allocate some memory on the tape. Contrary to simple variables (as x, y, etc.). In order to get d[u], one mark is not sufficient. We need to search the location where d[u] is written on the tape. For instance, we use
$d21:658$...
to say that d[2] equals 658.
All the steps of Dijkstra's algorithm implemented on a Turing machine make heavy use of back and forth move of the tapes between the locations where the data are stored on the tape.
You may find a video that shows a single-tape Turing machine executing Dijkstra's algorithm https://www.youtube.com/watch?v=LyQYK98POM8
The video gives a link to the online implementation.
That sounds like a good plan -- except you don't want to add $x$ to $x$; you want to add $x$ to a separate counter that starts at $0$.
Do you already have a machine for addition with the number representation you use (which preserves one of the operands on the tape and increases the other destructively)? Otherwise start by making that.
Alternatively if you're representing the integers in base-2 you could replicate the usual long multiplication algorithm:
Set T=0
While X != 0:
If the lowest bit of X is 1:
Set T=T+Y
End if
Remove the lowest bit from X
Append a 0 bit at the end low of Y
End while
The result is in T
This may not even be more complex to program, and will run faster (though that is typically not a relevant consideration when we talk about Turing machines. It might be a relevant difference here because it is more than a polynomial difference).
Best Answer
assuming input a#(1)b convert to a#(1)b#(2)c#(3)BLANK
Blank will be filled with sum. Make 2 cases for LSB of 'a'. Further divide 2 cases for LSB of 'b'. 'c' is the carry bit that is initially 0. Make seperate 2 cases for each of the four cases and update the carry bit on the way. Path is chosen based on if 'c' was 0 or 1.
Picture shows a rough sketch.
Final result will be reversed value of original sum. You reverse this again. Take the pic with a grain of salt. It is just a rough sketch. Nomenclature is not followed.