Exactly, memory and time are orthogonal, shift one and you must shift the other in the opposite direction to achieve the same goal (like the solutions run along a diagonal line between the axis).
I’m getting into speculation territory here but it seems intuitively correct (I’m pretty sure I’m going to find out if I’m in left field here):
Without having any formal cites or definitions, I’m sure there is some math behind the nature of the algorithm and how much (energy? not sure the right term) is contained within the code, contained within the CPU logic, contained within the memory being used and the amount of time to produce a result.
Ultimately it seems like there is a continuum of solutions to problems, from the fully enumerated (no algorithm required), to the nothing-enumerated-everything-calculated, but there is conservation of something (most likely energy).
Our current setup of having logic embedded in a CPU and having instructions in an algorithm that get executed and memory for storing state seems like it’s just compression of information and it resides somewhere along that continuum.
The 1986 Obfuscated C contest has a little messy gem (august.c) that calculates digits of e until it runs out of memory and dumps core. Thought of it because it’s the right year range for you.
It is not really a matter of “our current setup”, it is endemic to basically all math and logic. Computation represents the destruction of information. For instance, when you look at “2 + 2 = 4”, the result on the right is what we would consider useful but the part on the left, which we ultimately discard, contains more information. “e = mc^2” is more useful to most people than the pages and pages of arcane math that lead to it.
Computers do not “compress information” they destroy it in pursuit of a useful result. This is why they produce waste heat. The programmer generally tries to seek the most efficient path of destruction (if there is one, given the constraints of the working environment). Pages and pages could be put forth on the subject of optimization, its history, and how to optimize your optimization process (not get obsessive and do too much).
“compress” does seem like the wrong term, but so does “destruction”.
“transformation” (with conservation of energy) seems like the correct term.
Are you knowledgeable on this topic to the point I should trust the “destruction” term, or is it your opinion?
I googled and found this, but it was just the first link and I don’t know if it is the accepted theory or not:
“Chaitin’s Algorithmic Information Theory shows that information is
conserved under formal mathematical operations and, equivalently, under
computer operations.”
No, it is not my opinion. Computers literally destroy information. Imagine that you could read through and comprehend, at least nominally, Einstein’s math that arrives at “e = mc^2”. As soon as you understand it, you will start to mentally lose hold of the pages of formulae. They will not be physically lost (still on paper), but, unless you have a photographic memory, prettymuch all you will retain is the result. This is basically the manner in which computers destroy information. Chaitin’s theory is not really applicable to my point.
You see, CPUs are built out of logic gates, which consist of two wire (bits) going in and one going out, thereby irretrievably destroying half the information at hand. These gates are cascaded into more gates which cascade into more gates, so the level of information destruction scales geometrically. Programs, seen on a higher level, consume and discard large amounts of transient data as well, it is all but unavoidable.
Consider, for instance, the page you read on Chaitin’s theory. You may be able to remember the substance of what you read, even some key points, but you cannot recite the whole thing verbatim. The information still exists at the source, but you have destroyed a significant fraction of it in your mind (unless you have a really good memory).
So it is with a computer. The source data typically remains intact, but the result is highly condensed, being partially destroyed in the reduction/transformation process. And that is not counting the other data that is used and burned off in the process. Some of that data, may not physically be destroyed, but it becomes basically unreachable as the program has lost track of where to find it and probably has no use for it anyway (or it would have held onto it).
So, yes, “destruction” is kind of an extreme way to put it, but it really is not inaccurate.
I don’t see what you’re talking about unless you leave the logical world of software and talk about the hardware itself. I guarantee you I can create a Tower of Hanoi system that loses not one bit of information ever, so long as the hardware operates. I would only be limited by memory in the addition of new information collected from the operation of the system, so it can actual retain everything, and create new information.
Please tell me what I’m missing in what you are saying.
(and I’m dying to point out to the OP that I suggested the Tower of Hanoi yesterday, including a big finale)
Saying computers destroy information because transistors have multiple input wires and a single output wire is like saying cars destroy information because they have four wheels but only move along one road.
Ok, it sounds like you are saying this is accepted amongst computer scientists/mathematicians/information theorists…can you provide a link supporting this position? I’m not familiar with it, but I’m not an information theorist either.
Yup, credit where it is due, I was remiss in not citing the individual contributions to my thoughts - as I wrote, they were a distillation of the earlier bits of the thread, there wasn’t really anything new, I just put the bits together from the earlier posters.
Um…<shrug>… ok. Well, ok for some definitions of the relationship between those disparate analogues.
It’s easier to point out that a transistor as an entire information system destroys information, but as a component of an information system that doesn’t have to be the case. A computer can be a perfect data transformation system because it has memory.
Reading wiki I see that they do consider it a destruction of information (when heat is generated) which seems counter-intuitive.
Is the information considered destroyed because we can’t accurately measure the resulting heat (physical attributes of the particles) and therefore we can’t reconstruct the information once converted to heat?
Once you cross the boundary into hardware you’re stuck with the same physics and thermodynamics as everything else. But at the software level you are only limited by the hardware.
Unless you are talking about something else. I’ve been looking at the Chaitin wiki and didn’t see a mention of heat there. I don’t think the Tower of Hanoi or any other particular function has to ‘destroy information’ because it doesn’t require a string of undetermined complexity.
Part of it is the hardware thing, yes. Look at how the internals of a CPU works, you will see some internal information is discarded on just about every instruction, not counting the instructions themselves, which are read, run, deleted and replaced one after the other very quickly. Even with a cache, no instruction remains in the pipeline longer than it takes to execute and must be reloaded every time it is encountered.
But even if you wrote your code in a way that retains every transient value including the loop index (because it could not work recursively), you still eventually have to get your data to the screen or printer. If you try to roll your own code that destroys or discards absolutely no information (e.g., retains an index for every value you every put into a screen memory location), you will end up with a ridiculously cumbersome program that consumes far more memory than it should for the task.
If you want to write little experimental bits of code for community college courses, fine, but if you want to write something useful, you will find that it works best if you shuck the cruft, usually early and often.
Certainly. But in reference to the Tower of Hanoi, or ‘e=mc^2’, there’s no real difference regarding destruction of information. And outside of the hardware limits, all such destruction is done deliberately, not out of necessity. It’s just impractical to maintain that much storage. But so long as you have the input and there are no random factors, the little transient values can all be reproduced. It’s only randomness and lack of memory that make it impossible to retain all information.
The subject of computation and destruction of information is complex, and my memory is thin on the subject. Reversible computation, where the hardware stores the previous state can be shown to run without an increase in entropy, and can avoid some fundamental limits. However we have zero idea how to make such a computer.
The precise, correct statement of the role of entropy in computation was due to Landauer[sup]5[/sup], who showed that reversible, i.e. one-to-one, logical operations such as NOT can be performed without dissipation in principle, but that irreversible, many-to-one operations such as AND or[sup]8[/sup] ERASE require dissipation at least kB ln 2 for each bit of information lost. (ERASE is a one-bit logical operation that takes a bit, 0 or 1, and restores it to 0.) The argument behind Landauer’s principle can be readily understood[sup]37[/sup]. Essentially, the one-to-one dynamics of Hamiltonian systems implies that when a bit is erased the information that it contains has to go somewhere. If the information goes into observable degrees of freedom of the computer, such as another bit, then it has not been erased but merely moved; but if it goes into unobservable degrees of freedom such as the microscopic motion of molecules it results in an increase of entropy of at least kB ln 2.
Truly Reversible computation is impossible for the simple reason of infinite recursion. If you record the last operation, you must also, then, record that you recorded it. And then record that…
Edit: you could argue that’s implicit, but I argue that then we’re cheating. Besides, it’s trivial to reverse a given program at the software level, just keep a queue of every assembly instruction and its location in memory. Well, okay, it’s trivial assuming a single single-threaded process is running.
There were notional designs for reversible hardware. To state the obvious - it wasn’t something you would recognise as conventional . A log of state changes can be enough. However the log has to be self describing, otherwise you do indeed get into a recursive definition.
Reversible computing could be useful, if you could just, like, have a wrapped log queue. Like a security camera on a loop. Once a piece of code crashes, you have a way to rewind and try to capture the cause. I could see how in a multi-threaded environment, having a rewind option, so that errors caused by poor synchronization might be recovered, could well lead to sloppiness in development: programmers would just not worry about locks and coherence, just let the hardware/system clean their problems up for them.
As far as pertaining to crashing 80s computers, though, it looks like we may have drifted a bit.
Reversible computing was figured out in the 70s. You just need gates (or softare that simulates the gates) which can be reversed. And then build anything you want from that. Note that if a gate has 3 inputs, it has to have 3 outputs (1 or 2 of which are useful and the rest only needed for reversibility). It’s not done in real life since those extra outputs have to be either kept around or fed into the next stage. Both of which add cost to the circuit or computation.
“Destroying information” is one of those things which has very different meaning to different people. At a very abstract level, information can never be destroyed (which one of the issues about black hole properties). So if you took a book and burned it, the info is still there.
But in practice, if you burn a book, recovering the information isn’t going to happen. Ditto with a computer. Once the bits have been mixed up in a complex operation, you can’t recover the originals without special per-arrangements, like reversible computing.