Write a one-tape deterministic Turing machine to implement the BubbleSort algorithm. The input alphabet = {a,...

 

Transcribed Image Text:

Write a one-tape deterministic Turing machine to implement the BubbleSort algorithm. The input alphabet = {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 = {a, b, c, d}) Write a one-tape deterministic Turing machine to implement the BubbleSort algorithm. The input alphabet = {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 = {a, b, c, d})