Question

Given a list of numbers, could you build a Turing machine to sort them into non-decreasing order? Non-decreasing order is essentially the same thing as increasing order, except that it recognizes that some of the numbers might be repeated. Explain why this is or why this is not possible. Do not try to give an algorithm or even a description of how the machine would work--just an explanation as to why it is or is not possible.

Answer 1

First of thing you should understand if there is any algorithm for a problem to solve then definitely that problem can be solved using turing machine refer CHURCH THESIS.

Please Refer This detail information.

Abstract

For nondeterministic Turing machines with one work-tape and one-way input a lower time bound Ω(m2) on sorting m strings of length each is shown, which matches the upper bound. For the related Element Distinctness Problem with input of the same format we prove the upper bound O(m2) if = O(m/ log m), showing this problem to be easier than sorting. The bound O(m2) also holds for deterministic machines if = c+log m with constant c. For this problem Szepietowski has shown the bound Θ(m2 log m) on deterministic Turing machines without input tape.

1 Introduction

Sorting is among the most widely studied tasks in computer science. Many algorithms have been developed for computational models that treat the keys of items to be sorted as atomic units. There are however interesting solutions like radix-sort that access portions of the keys. The investigation of such algorithms clearly requires a model that processes its input on a bit-level. The traditional model in this field is the Turing machine. As discussed in Section 2, multi-tape Turing machines are quite efficient at solving the sorting problem. In the present work we consider the sorting problem for binary strings or equivalently natural numbers in binary encoding. This is no severe restriction, since pointers to data can be stored in the least significant digits. We denote the problem of sorting m strings of length by SORT(m, ), where we assume that m and are related by some easily computable function. When considering nondeterministic sorting procedures we require that within the given time bound at least one computation writes the sorted input on a work-tape and all other cells contain blanks. No terminating computation produces an incorrect output. A decision problem which is closely connected to sorting is the Element Distinctness Problem (EDP). The EDP asks whether m elements given as strings of bits each are pairwise different. We denote this problem by EDP(m, ). As a language recognition problem EDP can be defined in the following way: EDP(m, ) = {x1#x2# ··· #xm | xi ∈ {0, 1} , xi = xj for i = j}. Since on many computational models EDP can be efficiently reduced to sorting,lower bounds on the decision problem EDP carry over to the sorting problem.

2 Previous Work

It is well-known that deterministic Turing machines with three work-tapes can sort much faster than machines with one such tape. Using merge-sort and radixsort machines of the former type can solve SORT(m, ) in time O(m(log m)) and O(m2) resp. [Rei90, p. 152]. Radix-sort can be implemented on machines with two work-tapes by making two passes over the sequence of strings when sorting according to a bit, but for large (e.g., = m2) the resulting bound O(m2) is worse than sorting by selection. One of the factors in this bound can be replaced by log m with the help of a merge-sort strategy that first determines the final position of each string by counting. If the input-tape of a two-tape Turing machine is restricted to be read-only we obtain the off-line Turing machine investigated in [Wie92] by Wiedermann. He gave a nondeterministic solution running in time O(m3/2). A deterministic algorithm for Turing machines with a separate two-way input-tape having the same complexity was presented in [Pet08]. This bound cannot be improved in general by the lower bound from [DMS91]. The most restricted model we mention here is the single-tape machine that receives its input on the work-tape. For this model Wiedermann could show the bound Θ(m log m+2−1 m ) in [Wie92], which is better than the naive quadratic algorithm for small . The investigation of the EDP on Turing machines with a single work-tape was initiated by L´opez-Ortiz [LO94]. He proved the lower bound Ω(m2 log m) on the time necessary for a nondeterministic Turing machine without separate input-tape to accept the EDP with m elements of = k log m bits each for k ≥ 2. There is a straight-forward deterministic solution in time O(m2 log2 m) and L´opez-Ortiz conjectured that the latter bound was optimal. Szepietowski [Sze96] showed that the lower bound Ω(m2 log m) also holds for elements of size c + log m with constant c. In this case there is a matching upper bound. The nondeterministic version of the conjecture of L´opez-Ortiz was disproved in [Pet02] with a solution of complexity O(m2(log m)3/2(log log m)1/2). An even better algorithm in [BABP03] showed the lower bound to be tight in the case of nondeterministic machines, while the deterministic version of the conjecture turned out to be true. In [Pet08] the EDP was solved by Turing machines with a single work-tape and a separate two-way input-tape. For the EDP with m elements of size = O(m/ log2 m) a nondeterministic solution of time complexity O(m3/21/2) was presented, which is slightly faster than the sorting procedures mentioned above. In the present work we investigate computational models between the machines discussed above, namely Turing machines with one work-tape and a separate one-way input-tape. Probabilistic Turing machines of this kind have been investigated by Kalyanasundaram and Schnitger [KS92], who could show the lower bound Ω(m2/ log m) on EDP with elements of size 2 log m. We prove here that in the case of nondeterministic machines the EDP is easier than sorting by showing an optimal lower bound on sorting and a faster algorithm for EDP.