0
$\begingroup$

I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :

Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted array $A$) in $\log$ time ? That is, is it possible to simulate random access on a TM ?

My thoughts so far are that it is not possible, because the memory of a TM has to be accessed sequentially, e.g. in binary search, reading the element at $n/2$ in the array (first comparison for binary search) takes at least $n/2$ steps.

If it is indeed impossible, does the same hold for structures like binary trees ?

$\endgroup$
0
$\begingroup$

Can't be done.

Assuming the TM receives its input as $\langle x, A \rangle$ (i.e., $x$ followed by $A$) and that $x$ as well as the array contents are binary encoded, then the asymptotic log-time bound ensures almost all inputs are such that the TM is not even able to read past $x$, let alone search the array. Even if you bound the contents of the array (i.e., a constant number of values, one value per cell), the TM can only read up to the first $\log n$ entries for a list of size $n$; searching for an $x$ strictly larger than those entries will fail.

I am not sure how you intend to represent binary trees (with pointers?). I am sure it is the same case as above.

That being said, there are models which add random access capabilities to TMs, in particular random-access TMs. You might want to look into those.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.