There is given input – words is sequence of numbers: wi is number
in sequence, i is position. All of them are in written in binary
w1#,...#wk#i Prove that there exists deterministic
Turing machine which find i-th number in sorted sequence w in
I am not sure if I correctly solved it, so I ask for checking my reasoning. It seems to be fairly simple.
First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to n-th number)
Simply, we consider one by one each element of sequence and count how many elements is less than currently considered. If we count i−1 numbers, then we stop. It requires logarythmic(k) memory for counter. These counter can be reused (for each iteration).
Waht do you think ? Maybe some other approach to proving it ?
First let’s consider the case when numbers are unique. The idea is that for each element wt we count the number of elements in the sequence which are less than wt. After each loop on all elements of the sequence we check if there are i−1 elements less than wt then wt must be i-th element in the sorted sequence, so we halt with the output equal to wt.
proc(w, k, i) for t=0 to k counter = 0 for j=0 to k if w[t] > w[j] counter = counter + 1 if counter == i-1 then output w[t] and halt end-proc
Now, if numbers are not unique then we have to count duplicates as well
proc(w, k, i) for t=0 to k counter = 0 dups = 0 for j=0 to k skip if j == t if w[t] == w[j] dups = dups + 1 for j=0 to k if w[t] > w[j] counter = counter + 1 if counter+1 <= i AND i <= counter + dups+1 then output w[t] and halt end-proc
w w ... w[counter] w[t] w[t] ... w[t] .. \__________ __________/ \_____ ____/ \/ \/ all elements less than w[t] duplicates
Both procedures require only constant number of variables
dups whose lengths are O(log(k)). Your solution is similar to these algorithms so your approach is correct.