![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyHoly crap, I haven't updated in 3 weeks?
Well, in that time, we played a game of AGoT that went ridiculously long; our TV broke before Angus could find us a new one, but he found one shortly afterward; I did an interesting numerical experiment whose results I will presumably talk about some other time, but not now; I did yet more writing on the well-ordering paper; Dan (whose hands are feeling better now) and I played Guilty Gear for the first time in months; I've gotten to know the first years (and their capabilities in Smash) a bit better; I talked to someone about paperclip maximizers in a context you definitely wouldn't expect; I asked the board about doing more with the ICC mail server... yeah, I've got enough material for multiple entries here (well, at least two), but I don't much feel like writing them. Instead, here are some thoughts on models of computation.
Note: As I am someone who doesn't really know this stuff, I expect what follows is actually totally standard and I am just reinventing the basics. Because now that I actually write it down, it all seems really obvious. But it didn't when I was first thinking about it! So that was good to think about I guess. Well, I'm just going to write this down rather than go and look stuff up. :P Maybe I'll do that later.
So. If we want to talk about algorithmic complexity, we need to agree on a model of computation. And the standard one used is the multi-tape Turing machine. (Single-tape Turing machines obviously suck.) Of course, actual computers that we build don't much resemble multi-tape Turing machines; they're more like random-access machines. So why don't we consider that to be the standard model of computation? I mean, part of this is to make the math easier -- from what other people tell me, I gather that Turing machines are easier to reason about -- but is there any real reason we use a model where you only have linear access to memory, rather than random access? (I mean, we often do think about things in terms of a random-access model; everyone loves binary search. But I think multi-tape Turing machines are considered the standard model in algorithms research.)
I want to argue that the answer to this question is (probably) yes; and that furthermore, the answer is (probably) yes because we live in (mostly) Euclidean space rather than in (mostly) hyperbolic space, and that if we lived in (mostly) hyperbolic space, the random-access model would be preferable. I guess the lightspeed limit and the Bekenstein bound are also relevant.
(Side note: Apparently in the random-access model you can do multiplication in *linear* time? You have to admit, that sounds a little fishy.)
Anyway. You've got a computer. It's got a whole bunch of RAM, which it has random-access to. But not everything fits in RAM so it has a hard drive. It pretty much has random-access to the hard drive, too. Maybe not entirely, I'm not super clear on the details of how hard drives work. But I'm going to elide that point because I don't think it's important.
Of course not everything fits on the hard drive either. You need some way of extending the memory arbitrarily. Maybe it's hooked up to a whole network of computers with their own hard drives (using some protocol that allows network addresses to be arbitrarily long, of course). Maybe every so often it displays the message "need hard drive #[etc]" and you have to go fetch it from your warehouse of hard drives and swap it in. Preferably you have some automated process that does that for you.
The point is, some data is physically farther away than others. And such data takes further to get to. The time increases at least linearly with the distance; there's the speed of light limit. Let's assume for simplicity data with longer addresses is farther away (this has to be true in the limit). We don't have to imagine the read-head of the Turing machine travelling out there in a line, but we can just suppose that you're using something like a random-access machine, but every read instruction has an associated delay, which increases as the address to be read increases. But that by itself isn't enough to complete my argument. For instance, if it only increased linearly with the address length -- that is to say, logarithmically with the address -- it would be as good as random-access (since you'd need to write down the address before you could try to read from it, after all).
So why can't this happen? Fundamentally, there is a limit to how much data you can cram into a given volume of space (there's the Bekenstein bound, although it's possible I've horribly misunderstood it); not only is some data physically further away from others, it has to be. Meaning we have to consider the question, how much data can we store at a fixed distance r? That is to say, how does the surface area of a sphere of radius r in physical space increase with r?
Since we live in (mostly) Euclidean space, it increases quadratically (or polynomially, if we suppose we have extra dimensions we can access). Turning it around, the time to access data with a given address has to increase at least as the square root of the address, or at least as a stretched exponential in the length of the address. By contrast, if we lived in hyperbolic space, the surface area would increase exponentially, so the time to access data would only increase logarithmically in the address, i.e. linearly in the address length, and this would be as good as random-access.
Note that the argument is not quite complete: Increasing as a square root (or nth root) of the address is not quite the same as increasing linearly with the address; hopefully these are essentially equivalent (because otherwise it messes with my argument :P ), but it's not obvious to me (and honestly, I don't really intend to think about it; this isn't really my area). Also, I'm assuming random-access-but-with-linear-delay really is the same as multi-tape Turing machine, but I mean, that has to be true, right? Regardless, even if we assume square root (or nth root) instead of linear, I figure this at least has to be qualitatively different from random access, and considerably closer to multi-tape Turing machine, even if not actually the same as it.
-Harry
Well, in that time, we played a game of AGoT that went ridiculously long; our TV broke before Angus could find us a new one, but he found one shortly afterward; I did an interesting numerical experiment whose results I will presumably talk about some other time, but not now; I did yet more writing on the well-ordering paper; Dan (whose hands are feeling better now) and I played Guilty Gear for the first time in months; I've gotten to know the first years (and their capabilities in Smash) a bit better; I talked to someone about paperclip maximizers in a context you definitely wouldn't expect; I asked the board about doing more with the ICC mail server... yeah, I've got enough material for multiple entries here (well, at least two), but I don't much feel like writing them. Instead, here are some thoughts on models of computation.
Note: As I am someone who doesn't really know this stuff, I expect what follows is actually totally standard and I am just reinventing the basics. Because now that I actually write it down, it all seems really obvious. But it didn't when I was first thinking about it! So that was good to think about I guess. Well, I'm just going to write this down rather than go and look stuff up. :P Maybe I'll do that later.
So. If we want to talk about algorithmic complexity, we need to agree on a model of computation. And the standard one used is the multi-tape Turing machine. (Single-tape Turing machines obviously suck.) Of course, actual computers that we build don't much resemble multi-tape Turing machines; they're more like random-access machines. So why don't we consider that to be the standard model of computation? I mean, part of this is to make the math easier -- from what other people tell me, I gather that Turing machines are easier to reason about -- but is there any real reason we use a model where you only have linear access to memory, rather than random access? (I mean, we often do think about things in terms of a random-access model; everyone loves binary search. But I think multi-tape Turing machines are considered the standard model in algorithms research.)
I want to argue that the answer to this question is (probably) yes; and that furthermore, the answer is (probably) yes because we live in (mostly) Euclidean space rather than in (mostly) hyperbolic space, and that if we lived in (mostly) hyperbolic space, the random-access model would be preferable. I guess the lightspeed limit and the Bekenstein bound are also relevant.
(Side note: Apparently in the random-access model you can do multiplication in *linear* time? You have to admit, that sounds a little fishy.)
Anyway. You've got a computer. It's got a whole bunch of RAM, which it has random-access to. But not everything fits in RAM so it has a hard drive. It pretty much has random-access to the hard drive, too. Maybe not entirely, I'm not super clear on the details of how hard drives work. But I'm going to elide that point because I don't think it's important.
Of course not everything fits on the hard drive either. You need some way of extending the memory arbitrarily. Maybe it's hooked up to a whole network of computers with their own hard drives (using some protocol that allows network addresses to be arbitrarily long, of course). Maybe every so often it displays the message "need hard drive #[etc]" and you have to go fetch it from your warehouse of hard drives and swap it in. Preferably you have some automated process that does that for you.
The point is, some data is physically farther away than others. And such data takes further to get to. The time increases at least linearly with the distance; there's the speed of light limit. Let's assume for simplicity data with longer addresses is farther away (this has to be true in the limit). We don't have to imagine the read-head of the Turing machine travelling out there in a line, but we can just suppose that you're using something like a random-access machine, but every read instruction has an associated delay, which increases as the address to be read increases. But that by itself isn't enough to complete my argument. For instance, if it only increased linearly with the address length -- that is to say, logarithmically with the address -- it would be as good as random-access (since you'd need to write down the address before you could try to read from it, after all).
So why can't this happen? Fundamentally, there is a limit to how much data you can cram into a given volume of space (there's the Bekenstein bound, although it's possible I've horribly misunderstood it); not only is some data physically further away from others, it has to be. Meaning we have to consider the question, how much data can we store at a fixed distance r? That is to say, how does the surface area of a sphere of radius r in physical space increase with r?
Since we live in (mostly) Euclidean space, it increases quadratically (or polynomially, if we suppose we have extra dimensions we can access). Turning it around, the time to access data with a given address has to increase at least as the square root of the address, or at least as a stretched exponential in the length of the address. By contrast, if we lived in hyperbolic space, the surface area would increase exponentially, so the time to access data would only increase logarithmically in the address, i.e. linearly in the address length, and this would be as good as random-access.
Note that the argument is not quite complete: Increasing as a square root (or nth root) of the address is not quite the same as increasing linearly with the address; hopefully these are essentially equivalent (because otherwise it messes with my argument :P ), but it's not obvious to me (and honestly, I don't really intend to think about it; this isn't really my area). Also, I'm assuming random-access-but-with-linear-delay really is the same as multi-tape Turing machine, but I mean, that has to be true, right? Regardless, even if we assume square root (or nth root) instead of linear, I figure this at least has to be qualitatively different from random access, and considerably closer to multi-tape Turing machine, even if not actually the same as it.
-Harry
no subject
Date: 2012-10-07 04:05 am (UTC)no subject
Date: 2012-10-07 05:08 am (UTC)