-1
$\begingroup$

I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it can't perform a simple operation other models of computation can do with ease?

$\endgroup$

1 Answer 1

6
$\begingroup$

Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two different things.

Roughly speaking, computability is about what we are able to compute in a given model of computation. We believe Turing machines to be an universal model of computation. All powerful-enough (i.e., Turing complete) models are equivalent to a Turing Machine.

Complexity is about how long it takes to compute something (actually, this is not restricted to time). Different models of computation are not necessarily equivalent complexity-wise.

$\endgroup$
3
  • $\begingroup$ the issue isn't specifically with this algorithm, but more the limitations of turning machines in implementing abstract data structures. perhaps a better example would have been the travelling salesman, given that you can't implement a graph on a turning machine, how can you implement the travelling salesman problem. $\endgroup$
    – Glubs
    Commented Jul 15, 2021 at 10:20
  • 4
    $\begingroup$ What do you mean "you can't implement a graph on a Turing machine?" You can defnitely store a graph on a Turing machine's tape (for example by storing the list of the graph's edges). $\endgroup$
    – Steven
    Commented Jul 15, 2021 at 10:21
  • 6
    $\begingroup$ @Glubs By that logic, you can't "implement a graph" on a RAM machine either. Instead you store a sequence of bytes that encodes the structure of a graph. When we talk about the computational power of some model, it's usually implied that inputs and outputs are encoded in some reasonable way into a format that the model can handle. $\endgroup$ Commented Jul 15, 2021 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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