Subject: RE: [hackers-il] RE: Re: Concrete and Abstract Stuff (was: Re: Re : Re : Prerequisite learning?)

From: Ofir Carny <[email-masked]>
Date: Wed, 6 Mar 2002 08:52:22 +0200

> You're right that if you assume that your computer is compatible with a
> turing machine, i.e., there exists a constant C where each step you do
> in a turing machine you can do in up to C steps on your computer (and
> vice versa), then the actual details of the assembly language don't matter
> at all for O(...) calculations.

Actually no, not vice versa at least, turing machines don't suport random
memory access in constant (O(1)) time (at least the turing machines I know
of), and offcourse they have infinite memory to compensate for that...

	Ofir

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 6 Mar 2002 13:20:16 +0200

> of), and offcourse they have infinite memory to compensate for that...

Obviously, this point is moot in a computer with a finite amount of memory
(like ALL computers are). A turing machine can random-access a bit in 1GB in
memory in 2^30 steps, and here is your constant. Of course you can do things
a little more efficiently, but theoretically speaking, this huge constant is
enough, because it's a constant.

A theoretical computer with random-access to an infinite amount of memory
might indeed have more power than a turing machine. However, I'm not sure if
it really does.
It is also conceivable to have a computer where access to memory location n
takes not O(n) (like in a turing machine), not O(1) (like in a random-access
computer) but rather O(logn) (i.e., proportional to the length of the pointer
to n - imagine you need to send the address n on some bus). Like I said, I
have no idea how much power (if at all) these theoretical inventions have
over a standard deterministic turing machine.

-- 
Nadav Har'El                        |      Wednesday, Mar 6 2002, 22 Adar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |If you lost your left arm, your right arm
http://nadav.harel.org.il           |would be left.