in reply to
Re: Re: about Coolness, Impatience and Complexity
in thread about Coolness, Impatience and Complexity
Having been a computer scientists, I strongly disagree with
the statement that a Turing machine should be involved.
Not at all! We use elementary operations in a certain
computational model. That could be a Turing machine, but it
could also mean a pointer machine, a Von Neumann architecture
or something more abstract as arithmetic or geometry. Complexity analysis
for calculations on a modern computer certainly don't assume
a Turing machine as the underlaying model. You wouldn't be
able to do binary search in O (log N) time on a Turing machine.
You cannot achieve O (log N) on a Turing machine because
indexing in an array cannot be done in constant time on a
Turing machine - it's going to be at least linear in the amount
of tape used.