Write a one-tape deterministic Turing machine to implement the BubbleSort algori

Question

Write a one-tape deterministic Turing machine to implement the BubbleSort algorithm. The input alphabet sigma = {a, b}. When the computation halts, the contents of the tape should be in "sorted order" (i.e., all a's appear to the left of all b's). The Turing Machine should scan the tape from left-to-right, swapping any pair of adjacent items that are out-of-order. Then the Turing Machine should repeat this scan again. If the entire string is scanned, and no items are swapped, then the computation can halt. What is the big-Oh running time of your Turing Machine, given an input string of n symbols? (BONUS: write a BubbleSort Turing Machine for sigma = {a, b, c, d})

Explanation / Answer

Turing Machines

Turing Machine is informally defined as the machine that can solve any problem that can be solved. i.e., if there is a solution to a problem,then it can be implemented using turing machine.It takes as input a tape which is marked with a series of 1s and 0s.which could represent binary numbers.The machine also has a number of internal states.Depending on itsinternal state and the number read from the tape,the machine will write a 0 or a 1,move to a new internal state and will move left,right or end its program.

In deterministic Turing Machine, for an input symbol s and a state q, there will only be one transition possible. But in case of non-deterministic Turing Machine, it can have more than one transition for the same input symbol and state. Deterministic Turing Machines are usually used for solving polynomial time solvable problems or verifying polynomial time verifiable problems.

A Turing Machine is said to accept a string when the Turing Machine halts in a final state. In case of a Deterministic Turing Machine there is only one instance of the Turing Machine and the result can be directly observed. But for a Non-Deterministic Turing Machine, there will be many similar copies of the Turing Machine running simultaneously and if any one of its numerous offspring halts in a final state, then the string is said to be accepted.

The halting problem of Turing Machine states that, given a Turing Machine and an input string, we cannot decide whether the Turing Machine will halt for the input string. Let us consider an example.Say, halting problem is solvable. Now consider two algorithms halts(X, Y) and diagonal(X) (and by definition there exist two Turing Machines that implements these algorithms). The halts algorithm described here is a realization of the solution to the halting problem of Turing Machines. halts have two inputs: X, configuration of a Turing Machine and Y , a string. halts(X, Y) returns true if the Turing Machine X halts for input Y and returns false if the Turing Machine X do not halt for input Y. diagonal(X) is defined as:diagonal (X){a: if halts(X,X) then goto a else halt }i.e., diagonal(X) loops infinitely if the Turing Machine X halts for the input X (i.e., its own configuration) and halts otherwise. Now, consider the case when we feed the configuration of the Turing Machine implementing the diagonal problem itself as the input to the diagonal Turing Machine. This means that, if the algorithm halts says the Turing Machine diagonal accepts the configuration of diagonal, then it loops forever.But in fact the actual diagonal should halt. Also, if halts algorithm says that diagonal will not accept the configuration of diagonal then it will halt, whereas it should not have. In fact,diagonal says it will halt when it will not halt and vice versa, which is a contradiction. Thus,we can say that the only assumption we made,i.e., halting problem of Turing Machine is solvable and hence the existence of an algorithm halts, is wrong.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.