91Ó°ÊÓ

Design a Turing-machine with alphabet \(\\{\triangleright, 0, A, B\\}\) that takes as input any string \(\alpha\) of \(A^{\prime}\) s and \(B\) 's and duplicates them to produce an output of the form \(\alpha \alpha\). (E.g. input \(A B B A\) should result in output \(A B B A A B B A\) ).

Alphabetical?: Design a Turing-machine with alphabet \(\\{\triangleright, 0, A, B\\}\) that when given as input a finite sequence of \(A^{\prime} s\) and \(B^{\prime}\) s checks to see if all the \(A^{\prime}\) s appear to the left of all the \(B^{\prime}\) s or not. The machine should leave the input string on the tape, and either halt if the string is "alphabetical", or loop forever if the string is not.

Subtraction: Design a Turing machine that when given an input of two non-empty strings of strokes of length \(n\) and \(m,\) where \(n>m,\) computes the function \(f(n, m)=n-m\).

Design a Turing machine to compute the function \(\min (x, y)\) where \(x\) and \(y\) are positive integers represented on the tape by strings of 1 's separated by a 0 . You may use additional symbols in the alphabet of the machine. The function min selects the smallest value from its arguments, so \(\min (3,5)=\) \(3, \min (20,16)=16,\) and \(\min (4,4)=4,\) and so on.