Binary search in log time on a Turing Machine

Question

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 ?

Answer 1

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.