How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of $B$.

Then, I understood how it works for some cases, but I wonder in how I can to make a Turing Machine that compute the shortest path of a graph, I know algorithms like Kruskal, Prim or Dijkstra, but I have no idea in how to do this in a turing machine. I thought maybe with multiple tapes, but I'm not sure.

Solution 1:

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.