Presumably, even without atomic operations, there's still some reasonable notion of state (in the Markov sense). For another much simpler example, you can consider a mechanical system like a pendulum; it's a continuous-time system so there's certainly no notion of an atomic operation; nevertheless if you can measure simultaneously the bob's position and its velocity, then you can in principle predict what it will do in the future.
I think there is another relevant concept though, and that is the Lyapunov exponent. In a nutshell, since the brain is analog, any copy of its state will be imperfect, and hence a duplicate brain started from that state will diverge in operation from the original brain, at a rate characterized by this number.
What I meant in particular was that, since the plotting facilities are tied closely to MATLAB, it's possible to do things like build interactive simulations, and do real-time animation. AFAIK the only way to do animated plots with Octave+GNUplot is to pre-generate a sequence and then play it back like a movie, which would leave much to be desired. That said, I have admittedly not invested much time in trying to get GNUplot to do this sort of thing so it may actually be possible; if it is I wouldn't mind a pointer to e.g. a tutorial.
Python+matplotlib seemed very promising though. I liked them when I tried that combo out, but not enough to switch (mainly, MATLAB's matrix/array syntax is kind of wonderful).
I'm sometimes tempted to just use some nice C++ math libraries and do everything there, though; code can be an order of magnitude faster or more than either Python or MATLAB. E.g., a one-off script to solve a particular PDE took about 10 minutes to run in MATLAB (it was stuff that couldn't be vectorized well); nearly identical C++ code ran in about 10 seconds. Likewise (another example), for a project in planning algorithms for a class I was auditing, one team implemented a very clever algorithm in Python and another did something more naive in C++; the C++ team's planner was much faster despite being "dumber" simply because of the interpreter overhead that the Python team was saddled with. So I'm tempted by combos like C++ with the 'eigen' library.
Given any positive 'epsilon,' I can compute a rational number, in finite time, which approximates 'pi + e' to within 'epsilon.' That's all that's needed for computability.
On the plus side, everybody else is just throwing out perfectly good (but bulky) CRTs, so you should be able to get nice big ones for cheap; just use craigslist.
I guess another option is to buy plasma. It's basically CRT, just with gas discharge instead of an electron gun. But it's still phosphors generating the colors. Granted, they only really sell plasma TVs and not computer monitors, and burn-in will also be a major problem.
LED may also do what you want; AFAIK those things react very quickly.
A rational number class seems like a better solution, though there are some issues with representing every number as a ratio of integers... For instance, you need extremely large numerators as your denominators get large. For another, you need to keep computing gcfs to reduce your fractions. Still, this is the approach used in some calculator programs.
I wonder if a continued fraction representation would have advantages -- and if it has ever been used as a number representation in practice? It seems like it'd be very expensive, but I'd need to give it some thought...
For this purpose -- vector animation -- Flash honestly is the best thing out there and I'm not sure I want to see it go (though open standard are always good). I think people are more up in arms about Flash video in particular, which is too widespread given that it's both proprietary and a resource hog.
You definitely raise an interesting point though, and I wonder if an OSS project to do what you describe exists. Googling turns up this note on the inkscape roadmap which indicates that this is in their long term plans. Apparently another project, MadSwatter also exists, but I know nothing about it.
Given the amount of time it has taken for the Gimp to become a strong competitor to Photoshop, I do however suspect that Flash's reign in the vector-animation arena is hardly over.
I'm not sure I really see anything wrong with that. The language doesn't matter a ton; intro CS should really be about basic algorithms with the language really just being a vehicle for that.
(On a related note, I cried when I saw the homework the intro CS students did at my uni; for several weeks it was all just about using Java's Swing API! It should have been about basic data structures! Trees and heaps! Sorting and hashing! Parsing expressions! Not just learning an API; there's nothing fundamental about that... spend a week on it maybe so students learn what it's like to do GUI programming, but no more than that...)
Indeed; my "while ago" was meiosis (I'll admit I had to look that word up to remember it), but I didn't really give enough context for that to be clear!
They did that a while ago; they have an observatory and host astronomy conferences. Obviously it's an attempt to live down what their predecessors did to Galileo, but I welcome it.
Damnit, logic is just a formal system; it's a machine that you put assumptions into to produce other statements which are true so long as the assumptions are. That's it. "Logical" is not a synonym for "correct."
As for your argument with GP: Personally, I don't think GP said anything particularly extreme. He's probably not even vegetarian.
I think it depends on how far away the simulated scene is. Outside of a meter or so our stereo vision really doesn't do much. And also outside of that range (maybe a little further) the rays are close enough to parallel that it probably doesn't matter whether the system is tracking the head or the chest.
Sociological studies of hunter-gatherer societies have indicated that they even now have more free time than we do, not less. Moreover, it was only within the last 400-500 years that agricultural societies began to overtake hunter-gatherers in terms of nutrition (as measured by looking at the height of skeletons, and signs of the presence of malnutrition-related diseases). In other words, it was only very recently that agricultural civilization became good not just for those at the top but also for the majority.
The argument, then, for why agricultural civilization came to dominate the world even if it did not result in a better quality of life is this: Although the diet of cheap carbohydrates provided by agriculture did not result in healthy people, it did provide energy to sustain more people (albeit with a lower quality of life), whereas hunter-gatherer civilizations need to practice contraception and infanticide (and they did, and do, both) to avoid overexploiting their range. The societies with larger populations (the agricultural ones) were, in turn, able to field armies and otherwise exert power in ways that hunter-gatherers were not, and in this way also out-competed them.
In other words, until very recently, if you wanted to create a large and powerful society at the expense of individual health and leisure time, your best bet was to practice agriculture. If you wanted to create a small society of well-nourished and healthy people with more leisure time at the expense of collective power, you'd want to pick the hunter-gatherer lifestyle. And even now, although hunter-gatherers no longer have the nutritional advantage, they still win on leisure time.
I recently came to understand the singularity, and now that I do the argument is pretty funny; it basically is the result of a bad mathematical model.
Here's the idea: Suppose you built a computer to design a new computer twice as fast as itself, whose job is the same, and so on for its children, ad infinitum.
The first computer takes 1 day to do its job. Its speed is 1 exaflop.
The second computer takes 1/2 day to do its job. Its speed is 2 exaflops.
The third computer takes 1/4 day to do its job. Its speed is 4 exaflops.
...and so on.
Hence the total time it takes all the (infinite) computers in this series to work is given by the convergent geometric series,
1 + 1/2 + 1/4 + 1/8 +... = 2 days.
In other words, you design an infinite number of computers in finite time. And in this finite time, you've managed to produce infinitely fast computers, since their speeds go with 2^N. So the event referred to as "the singularity" is not called this just out of a love for words that sound like they belong in bad Star Trek dialogue; rather it is literally a mathematical singularity of the day-number--to-computer-speed map.
Geeks and nerds like the free range freedoms of the USA not gilded gulags.
Then why do they go to grad school? Hell, it would seem that this is precisely running away from capitalism. Why do they accept small government-funded stipends instead of better salaries in industry?
Russia, and Eastern Europe more generally, still produce many top-notch mathematicians (two thirds of the theorems I study are named after Russians) and programmers (just look at the Google code contest finalist lists). I wonder if there's simply a cultural component, and that they simply hold those who do abstract thinking in higher esteem.
What might be puzzling in the Miegakure game is the direction of gravity in the fourth dimension. The preferably easiest configuration is to let the gravity to have no effect.
From the video it looks to me like gravity is either the constant 4-vector (0,0,-1,-1), or varies depending on the three dimensions currently being displayed.
I hope it's the former, as that's more consistent. Furthermore, with this method there's no way to select a subset of the three axes without getting one that has gravity; this is probably a desirable property.
The one issue though would be computing the intersection of your 4d cubes with your 3d subspace as you do this interpolation, since your intermediate shapes won't be cubes...
Actually even this isn't too hard. Your 4d cube is the intersection of 2*4=8 halfplanes in 4d, so what you need to do is compute the intersection of this with the 3d subspace you're viewing (which is a 1d equality constraint). The intersection of each cube plane (a 3d subspace) with your viewing subspace (a 1d constraint) is a 2d plane. You've got 8 of these, so you've just reduced the problem to finding the convex polyhedron which is the intersection of 8 halfplanes in 3d. This is precisely what people have been doing with e.g. BSP trees for years. Or, even better, there are some fast plane-sweep algorithms from computational geometry to do this that I'm sure you can just pull in from a library (e.g. CGAL). Done!
Watching the video, it appears (1) that the objects are all cubes, and (2) that all movement (in all dimensions) is in cube-sized jumps (although these are animated smoothly). This makes me think that the underlying representation is as 4d voxels.
If I'm counting cubes right, then the world shown is about 9x4x6 cube-units in the x,y,z-dimensions, and maybe 4 cube-units in the w-dimension. So you need a 9x4x6x4 voxel grid; that's 864 voxels, and can be represented as a bitfield with just 27 32-bit integers. Not bad at all.
From reading the website, it seems that one can simply choose which three dimensions you see on the screen at any time. In the video, the ring they show lives in a 2d slice of the voxel grid. Then there are two axes which are orthogonal to this slice, and it appears that when in the video they "go into the fourth dimension" what they are doing is switching between which of these two dimensions they are appending to the two the rings lives in to get the three dimensions they display.
I wonder if they enforce that you select dimensions in a way that is orientation-preserving (e.g., you can't go (x,y,z) ---[swap z/w]---> (x,y,w)--->[swap y/z]--->(x,z,w)--->[swap w/y]--->(x,z,y) )?
Anyway, it seems that this "toggling dimensions" thing is not animated in any particularly tricky way. What would be absolutely awesome though is if they, as you suggested in your post, actually animated a continuous rotation between the two. Since each exchange only swaps two coordinates, each rotation is really a 2d rotation, and can be represented as a Givens rotation; all they need to do is interpolate the angle. The one issue though would be computing the intersection of your 4d cubes with your 3d subspace as you do this interpolation, since your intermediate shapes won't be cubes...
This makes a part of me wonder if the developers did send Randall an early pre-pre-prerelease version not available to the general public so that he would mention it in his comic and generate buzz....
I'm not sure what the 2D representation of a torus would be..?
Unless this is intentional, I think you've got it backwards... Gable Snarky (GP) was talking about adding dimensions; you're talking about removing them.
Anyway, this is still a question we can answer... in one of two ways, depending on what we want:
The first is that we can always consider 2d slices of the torus-embedded-in-3d donut; these are either concentric curves (which are circles if the plane is orthogonal to the central axis of the torus), a pair of disjoint closed curves (which are circles if the plane contains the central axis), or, in the degenerate cases of the plane being tangent to the torus, either a single circle or a single point.
The second is that, topologically, the usual torus-embedded-in-3d is a 2-dimensional manifold called, naturally enough, the 2-torus (denoted T^2); this manifold is the cartesian product of a circle (the 1-sphere, S^1) with itself; i.e., S^1 x S^1. Hence another way to generalize the concept of a torus to n dimensions is to define the n-torus as the cartesian product S^1 x S^1 x... x S^1 of the circle n times with itself. This actually is the convention people use. Note however that while this defines the topology of this object (how things are connected), it does not define its geometry (how far apart things are). There is a natural way to define a metric on this space (as the square-root-of-sum-of-squares of the distances in each direction along the circles), but unfortunately I do not think this agrees with the usual "2-torus is a donut" picture (since the inner radius is smaller than the outer radius).
Slashdot Mirror
Presumably, even without atomic operations, there's still some reasonable notion of state (in the Markov sense). For another much simpler example, you can consider a mechanical system like a pendulum; it's a continuous-time system so there's certainly no notion of an atomic operation; nevertheless if you can measure simultaneously the bob's position and its velocity, then you can in principle predict what it will do in the future.
I think there is another relevant concept though, and that is the Lyapunov exponent. In a nutshell, since the brain is analog, any copy of its state will be imperfect, and hence a duplicate brain started from that state will diverge in operation from the original brain, at a rate characterized by this number.
Sometimes I think that parallel programming isn't a "new challenge" but rather something that people do every day with VHDL and Verilog...
(Insert your own musings about FPGAs and CPUs and the various tradeoffs to be made between these two extremes.)
What I meant in particular was that, since the plotting facilities are tied closely to MATLAB, it's possible to do things like build interactive simulations, and do real-time animation. AFAIK the only way to do animated plots with Octave+GNUplot is to pre-generate a sequence and then play it back like a movie, which would leave much to be desired. That said, I have admittedly not invested much time in trying to get GNUplot to do this sort of thing so it may actually be possible; if it is I wouldn't mind a pointer to e.g. a tutorial.
Python+matplotlib seemed very promising though. I liked them when I tried that combo out, but not enough to switch (mainly, MATLAB's matrix/array syntax is kind of wonderful).
I'm sometimes tempted to just use some nice C++ math libraries and do everything there, though; code can be an order of magnitude faster or more than either Python or MATLAB. E.g., a one-off script to solve a particular PDE took about 10 minutes to run in MATLAB (it was stuff that couldn't be vectorized well); nearly identical C++ code ran in about 10 seconds. Likewise (another example), for a project in planning algorithms for a class I was auditing, one team implemented a very clever algorithm in Python and another did something more naive in C++; the C++ team's planner was much faster despite being "dumber" simply because of the interpreter overhead that the Python team was saddled with. So I'm tempted by combos like C++ with the 'eigen' library.
Given any positive 'epsilon,' I can compute a rational number, in finite time, which approximates 'pi + e' to within 'epsilon.' That's all that's needed for computability.
See computable number.
What was surprising to me is that not all reals are computable in this sense; an example is what the Specker sequence converges to.
This shouldn't have been surprising though, since it retrospect it's obvious that computer programs are countable whereas the reals aren't...
I don't know what you mean; you can do a lot with handle graphics in MATLAB...
On the plus side, everybody else is just throwing out perfectly good (but bulky) CRTs, so you should be able to get nice big ones for cheap; just use craigslist.
I guess another option is to buy plasma. It's basically CRT, just with gas discharge instead of an electron gun. But it's still phosphors generating the colors. Granted, they only really sell plasma TVs and not computer monitors, and burn-in will also be a major problem.
LED may also do what you want; AFAIK those things react very quickly.
A rational number class seems like a better solution, though there are some issues with representing every number as a ratio of integers... For instance, you need extremely large numerators as your denominators get large. For another, you need to keep computing gcfs to reduce your fractions. Still, this is the approach used in some calculator programs.
I wonder if a continued fraction representation would have advantages -- and if it has ever been used as a number representation in practice? It seems like it'd be very expensive, but I'd need to give it some thought...
For this purpose -- vector animation -- Flash honestly is the best thing out there and I'm not sure I want to see it go (though open standard are always good). I think people are more up in arms about Flash video in particular, which is too widespread given that it's both proprietary and a resource hog.
You definitely raise an interesting point though, and I wonder if an OSS project to do what you describe exists. Googling turns up this note on the inkscape roadmap which indicates that this is in their long term plans. Apparently another project, MadSwatter also exists, but I know nothing about it.
Given the amount of time it has taken for the Gimp to become a strong competitor to Photoshop, I do however suspect that Flash's reign in the vector-animation arena is hardly over.
I'm not sure I really see anything wrong with that. The language doesn't matter a ton; intro CS should really be about basic algorithms with the language really just being a vehicle for that.
(On a related note, I cried when I saw the homework the intro CS students did at my uni; for several weeks it was all just about using Java's Swing API! It should have been about basic data structures! Trees and heaps! Sorting and hashing! Parsing expressions! Not just learning an API; there's nothing fundamental about that... spend a week on it maybe so students learn what it's like to do GUI programming, but no more than that...)
Indeed; my "while ago" was meiosis (I'll admit I had to look that word up to remember it), but I didn't really give enough context for that to be clear!
They did that a while ago; they have an observatory and host astronomy conferences. Obviously it's an attempt to live down what their predecessors did to Galileo, but I welcome it.
This is very interesting to me. Do you have a source?
beyond reason or logic
Damnit, logic is just a formal system; it's a machine that you put assumptions into to produce other statements which are true so long as the assumptions are. That's it. "Logical" is not a synonym for "correct."
As for your argument with GP: Personally, I don't think GP said anything particularly extreme. He's probably not even vegetarian.
I think it depends on how far away the simulated scene is. Outside of a meter or so our stereo vision really doesn't do much. And also outside of that range (maybe a little further) the rays are close enough to parallel that it probably doesn't matter whether the system is tracking the head or the chest.
[I'm channeling Jared Diamond and The Third Chimpanzee here.]
Sociological studies of hunter-gatherer societies have indicated that they even now have more free time than we do, not less. Moreover, it was only within the last 400-500 years that agricultural societies began to overtake hunter-gatherers in terms of nutrition (as measured by looking at the height of skeletons, and signs of the presence of malnutrition-related diseases). In other words, it was only very recently that agricultural civilization became good not just for those at the top but also for the majority.
The argument, then, for why agricultural civilization came to dominate the world even if it did not result in a better quality of life is this: Although the diet of cheap carbohydrates provided by agriculture did not result in healthy people, it did provide energy to sustain more people (albeit with a lower quality of life), whereas hunter-gatherer civilizations need to practice contraception and infanticide (and they did, and do, both) to avoid overexploiting their range. The societies with larger populations (the agricultural ones) were, in turn, able to field armies and otherwise exert power in ways that hunter-gatherers were not, and in this way also out-competed them.
In other words, until very recently, if you wanted to create a large and powerful society at the expense of individual health and leisure time, your best bet was to practice agriculture. If you wanted to create a small society of well-nourished and healthy people with more leisure time at the expense of collective power, you'd want to pick the hunter-gatherer lifestyle. And even now, although hunter-gatherers no longer have the nutritional advantage, they still win on leisure time.
I recently came to understand the singularity, and now that I do the argument is pretty funny; it basically is the result of a bad mathematical model.
Here's the idea: Suppose you built a computer to design a new computer twice as fast as itself, whose job is the same, and so on for its children, ad infinitum.
The first computer takes 1 day to do its job. Its speed is 1 exaflop.
The second computer takes 1/2 day to do its job. Its speed is 2 exaflops.
The third computer takes 1/4 day to do its job. Its speed is 4 exaflops.
...and so on.
Hence the total time it takes all the (infinite) computers in this series to work is given by the convergent geometric series,
1 + 1/2 + 1/4 + 1/8 + ... = 2 days.
In other words, you design an infinite number of computers in finite time. And in this finite time, you've managed to produce infinitely fast computers, since their speeds go with 2^N. So the event referred to as "the singularity" is not called this just out of a love for words that sound like they belong in bad Star Trek dialogue; rather it is literally a mathematical singularity of the day-number--to-computer-speed map.
Kind of silly, no?
Geeks and nerds like the free range freedoms of the USA not gilded gulags.
Then why do they go to grad school? Hell, it would seem that this is precisely running away from capitalism. Why do they accept small government-funded stipends instead of better salaries in industry?
Russia, and Eastern Europe more generally, still produce many top-notch mathematicians (two thirds of the theorems I study are named after Russians) and programmers (just look at the Google code contest finalist lists). I wonder if there's simply a cultural component, and that they simply hold those who do abstract thinking in higher esteem.
My phone is 7.5 years old now, and it will make me very sad when (If?! Hope springs...) it dies.
What might be puzzling in the Miegakure game is the direction of gravity in the fourth dimension. The preferably easiest configuration is to let the gravity to have no effect.
From the video it looks to me like gravity is either the constant 4-vector (0,0,-1,-1), or varies depending on the three dimensions currently being displayed.
I hope it's the former, as that's more consistent. Furthermore, with this method there's no way to select a subset of the three axes without getting one that has gravity; this is probably a desirable property.
To reply to my own post....
The one issue though would be computing the intersection of your 4d cubes with your 3d subspace as you do this interpolation, since your intermediate shapes won't be cubes...
Actually even this isn't too hard. Your 4d cube is the intersection of 2*4=8 halfplanes in 4d, so what you need to do is compute the intersection of this with the 3d subspace you're viewing (which is a 1d equality constraint). The intersection of each cube plane (a 3d subspace) with your viewing subspace (a 1d constraint) is a 2d plane. You've got 8 of these, so you've just reduced the problem to finding the convex polyhedron which is the intersection of 8 halfplanes in 3d. This is precisely what people have been doing with e.g. BSP trees for years. Or, even better, there are some fast plane-sweep algorithms from computational geometry to do this that I'm sure you can just pull in from a library (e.g. CGAL). Done!
Watching the video, it appears (1) that the objects are all cubes, and (2) that all movement (in all dimensions) is in cube-sized jumps (although these are animated smoothly). This makes me think that the underlying representation is as 4d voxels.
If I'm counting cubes right, then the world shown is about 9x4x6 cube-units in the x,y,z-dimensions, and maybe 4 cube-units in the w-dimension. So you need a 9x4x6x4 voxel grid; that's 864 voxels, and can be represented as a bitfield with just 27 32-bit integers. Not bad at all.
From reading the website, it seems that one can simply choose which three dimensions you see on the screen at any time. In the video, the ring they show lives in a 2d slice of the voxel grid. Then there are two axes which are orthogonal to this slice, and it appears that when in the video they "go into the fourth dimension" what they are doing is switching between which of these two dimensions they are appending to the two the rings lives in to get the three dimensions they display.
I wonder if they enforce that you select dimensions in a way that is orientation-preserving (e.g., you can't go (x,y,z) ---[swap z/w]---> (x,y,w)--->[swap y/z]--->(x,z,w)--->[swap w/y]--->(x,z,y) )?
Anyway, it seems that this "toggling dimensions" thing is not animated in any particularly tricky way. What would be absolutely awesome though is if they, as you suggested in your post, actually animated a continuous rotation between the two. Since each exchange only swaps two coordinates, each rotation is really a 2d rotation, and can be represented as a Givens rotation; all they need to do is interpolate the angle. The one issue though would be computing the intersection of your 4d cubes with your 3d subspace as you do this interpolation, since your intermediate shapes won't be cubes...
This makes a part of me wonder if the developers did send Randall an early pre-pre-prerelease version not available to the general public so that he would mention it in his comic and generate buzz....
I'm not sure what the 2D representation of a torus would be..?
Unless this is intentional, I think you've got it backwards... Gable Snarky (GP) was talking about adding dimensions; you're talking about removing them.
Anyway, this is still a question we can answer... in one of two ways, depending on what we want:
The first is that we can always consider 2d slices of the torus-embedded-in-3d donut; these are either concentric curves (which are circles if the plane is orthogonal to the central axis of the torus), a pair of disjoint closed curves (which are circles if the plane contains the central axis), or, in the degenerate cases of the plane being tangent to the torus, either a single circle or a single point.
The second is that, topologically, the usual torus-embedded-in-3d is a 2-dimensional manifold called, naturally enough, the 2-torus (denoted T^2); this manifold is the cartesian product of a circle (the 1-sphere, S^1) with itself; i.e., S^1 x S^1. Hence another way to generalize the concept of a torus to n dimensions is to define the n-torus as the cartesian product S^1 x S^1 x ... x S^1 of the circle n times with itself. This actually is the convention people use. Note however that while this defines the topology of this object (how things are connected), it does not define its geometry (how far apart things are). There is a natural way to define a metric on this space (as the square-root-of-sum-of-squares of the distances in each direction along the circles), but unfortunately I do not think this agrees with the usual "2-torus is a donut" picture (since the inner radius is smaller than the outer radius).