Hey, as a once (medium long ago) CS major myself, I'd like to comment on your question. I think you're not really referring to Godel's Incompleteness Theorem, which relates more to axiomatic systems then it does to computer programs / algorithms, but to Turing's proof that the halting problem is algorithmically undecidable. The halting problem here is the problem of deciding whether a certain algorithm will run forever or ever halt. Algorithmically undecidable here means that it is impossible for you to build an algorithm such that for any given input program P, your algorithm will say whether or not the program P will ever halt. Important remark: this does not mean that it is impossible for you to prove that a specific program P1 halts or doesn't halt. It just means that it is impossible to write down an algorithm for doing it in all cases. It is even impossible to decide for which cases it is possible and for which not.
A consequence (or more generalized version if you will) of the fact that the halting problem is algorithmically undecidable is that the static analysis problem is also algorithmically undecidable. Static analysis here is the task of deciding whether a program P satisifies a specification S. You can not write an algorithm such that for any combination (S,P) the algorithm will tell you whether the program satisfies the spec or not. That again does not mean that it is impossible to prove that an individual program P1 satisfies an individual specification S1, which appears to be the case here.
To quote wikipedia on the halting problem:
http://en.wikipedia.org/wiki/Halting_problem
While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack. Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof. But each proof has to be developed specifically for the algorithm at hand; there is no mechanical, general way to determine whether algorithms on a Turing machine halt. However, there are some heuristics that can be used in an automated fashion to attempt to construct a proof, which succeed frequently on typical programs. This field of research is known as automated termination analysis.
It says a lot about the world that no other nation yet has the 1st and 2nd amendment.
Just out of curiosity, is this supposed to say something about the US or about the rest of the world? In the latter case, what exactly is the fact that the other democracies of the world did not choose to make the right to keep firearms in the house a constitutional right supposed to say about them?
well, you may not be a lawyer, but this is probably the most enlightening and insightful (not to mention most on-topic) comment in the entire thread. too bad we have to scroll through an entire page of fanboyish discussions to get to it:-)
Tip of the hat to you, sir.
Gotta love that link between the hardware limitations and the software concepts that may seem fancy but are essentially only built to get around them. I believe someone once called it "the law of leaky abstractions" - would be interesting to see what the new limitations would be if you start combining solid-state storage with pervasive multiprocessing, i.e. what can you do with a multi-processor multi-sdd server that you can not do with a single-processor single-hard drive server?
I think TFA is pretty right on the money that parallellization and massive use of SSD could cause some pretty fundamental changes in how we approach database optimization - if I were to imagine that rack that I'm staring at being filled with SSD drives and processors instead of with nothing but hard drives... locality of data takes on a whole new meaning if you don't require data to be on the same sector of the HD, but rather want certain sets of data to be stored on storage chips located around the same processor chips to avoid having to overload your busses.
Then again, I haven't been in this game for so long, so maybe I'm overestimating the impact. Oldtimer opinion would be very welcome.
Shame that the video...
on
I Will Derive
·
· Score: 1
Yes you can. Some examples:
- replace "add 1024" with "substract -1024"
- replace "if greater then 100" with "if greater then or equal to 99"
- replace "copy a to b, copy c to d" by "copy c to d, copy a to b"
Just have a look at any assembly language and use your imagination. To make matters even simpler, there are operators which completely ignore certain parameters (e.g. a JUMP operator which only takes 1 parameter leaves room for hidden data in the 2nd and 3rd operator field). There are plenty of instructions or combinations of instructions which leave room to such minor changes without any difference in execution. So for the steganographers, the goal would be to look for all of such instances in an executable, then agree on some kind of code (for example "add n" is a 1, "substract -n" is a 0). Semantically there is no difference, both codes will result in the exact same execution, but you found some wiggle room to leave a message.
It was reported on Slashdot a few years ago.
just out of curiosity: what do you mean by open voting? Are you suggesting a system where the vote results are released in their entirety, with a one-way anonymization? So for example, i submit my vote via internet, it's registered and i get a message saying "your vote has been registered, your check number is 123456789", and then later they release the full list and i can go verify that 123456789 has indeed been counted as a vote for party X? Because I would consider that a very good system, but I've never heard anyone suggest it before... Are there known downsides to such a system?
The most obvious reason for me would seem to be simply avoid responsibility for the API until it is fully matured? Surely, if they were to release their API for the entire multi-touch aspect of the iPhone and iPod Touch at this point, they would be in a position where they have a lot of responsibilities:
* extensively documenting the API for a broad base instead of only for internal usage * testing for possible bugs for usecases which are not relevant in Apple's internal usage * making it feature complete * making it secure * when upgrading the API, supporting older applications built on that API (in other words, keeping full backwards compatibility)
All in all, this can be summed up as the basic fact that officially releasing the "mini OS X" that Apple uses on its portable devices as a development platform requires a whole different approach then simply using it themselves and not publishing it. All these responsibilities are easily avoided by simply not publishing the API and is a no-brainer if the company is on a tight deadline. Given the iPhone's short development lead time, i can fully understand that there was no time to get all of the above in order, so avoiding responsibility of the API for the time being seems like a logical thing to me.
That said, the above reason would steer them towards a tolerance stance regarding 'hackers', while Apple seems to be leaning more towards an 'active prosecution' stance, which i considere pretty much unjustified, together with the rest of the world.
Actually, that's what i thought at first as well - w00t, a full versioning file system in a mainstream os! But apparently, that's not quite it...
Time Machine simply does incremental back ups every night. It needs an external hard drive or a server to back up to. It's a backup utility, not a versioning file system.
Too bad, i kinda like where this was going: if they had gotten filesystem-level support for both versioning (Time Machine) & indexing (Spotlight) integrated with their X-SAN file system... every company in the world would want one of those babies:-) . Finding info on large project servers and keeping track of different versions of the same files are two of the most common time-consuming problems I have encountered on virtually every project I ever worked on.
Actually, you haven't said quite enough yet. What counts for caching is not bandwith, it's latency, and you haven't said a thing about that. Try fetching a 100MB file of a tape streamer against fetching it off your HD, i'll bet the tapestreamer outperforms your HD in bandwith. Doesn't mean jack shit, though.
What makes the VM on a hard drive so shitty is the fact that the heads have to be repositioned for every read and that, because of that, it takes ages to read non-sequential data. RAM and flash memories don't have this problem. If the extra delay caused by the USB bus being between the flash drive and the system bus is minimal, the flash drive shout outperform the hard drive any day.
It also features such songs as
"Honk if you want to plonk Zonk"
"Post-it now, Post-it later"
"Crap for Nerds, News for Turds!"
and the epic poem "This Guy Has Got To Be The Worst Slashdot Editor In The History Of Mankind"
I'll definitely go see it!
Just out of curiosity, are there any systems designed the other way around? I would think that making an OO design for the entire app, then letting a tool extract the structure for the database tables out of the classes would be a more logical approach then extracting the OO design out of the database tables?
Well, I'm not a mind reader, but I don't think that Steve Jobs' intent in the grand scheme of things is to become a boutique manufacturer. Apple sees the Intel roadmap as a path to a significantly greater market share, and that means hitting the mainstream, not picking up ten guys here and there.
I'd have to agree completely. Last year, if you asked 1000 computer users why they were buying a windows box instead of a Mac, the 2 most frequent answers would be "it's too expensive" and "I can't run my existing applications / games on it". By introducing the mac mini, they removed the first argument. By moving to intel and allowing windows dual-boot, they're removing the second. I'm guessing that apple actually DID ask people why they're not buying a mac. And i'm guessing they listened.
While I agree it doesn't have to be music, the beeps kinda seem worse to me... one idea i really like is partylines. Basically, everybody who's on hold can talk to each other. I used to work at a radio station where some of our DJ's would have the partyline on speaker during songs, and sometimes they'd just throw people on the air if they were being funny. We once had six guys who were singing along to a song, on the air, without knowing it. Hilarious stuff.
In tech support, it has some extra advantages. People could actually help each other out, if one has a problem that the other knows a solution to. Not sure if this would happen a lot in practice, but in theory it'd be nice...
Slashdot Mirror
Hey, as a once (medium long ago) CS major myself, I'd like to comment on your question. I think you're not really referring to Godel's Incompleteness Theorem, which relates more to axiomatic systems then it does to computer programs / algorithms, but to Turing's proof that the halting problem is algorithmically undecidable. The halting problem here is the problem of deciding whether a certain algorithm will run forever or ever halt. Algorithmically undecidable here means that it is impossible for you to build an algorithm such that for any given input program P, your algorithm will say whether or not the program P will ever halt. Important remark: this does not mean that it is impossible for you to prove that a specific program P1 halts or doesn't halt. It just means that it is impossible to write down an algorithm for doing it in all cases. It is even impossible to decide for which cases it is possible and for which not.
A consequence (or more generalized version if you will) of the fact that the halting problem is algorithmically undecidable is that the static analysis problem is also algorithmically undecidable. Static analysis here is the task of deciding whether a program P satisifies a specification S. You can not write an algorithm such that for any combination (S,P) the algorithm will tell you whether the program satisfies the spec or not. That again does not mean that it is impossible to prove that an individual program P1 satisfies an individual specification S1, which appears to be the case here.
To quote wikipedia on the halting problem:
http://en.wikipedia.org/wiki/Halting_problem
While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack. Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof. But each proof has to be developed specifically for the algorithm at hand; there is no mechanical, general way to determine whether algorithms on a Turing machine halt. However, there are some heuristics that can be used in an automated fashion to attempt to construct a proof, which succeed frequently on typical programs. This field of research is known as automated termination analysis.
It says a lot about the world that no other nation yet has the 1st and 2nd amendment.
Just out of curiosity, is this supposed to say something about the US or about the rest of the world? In the latter case, what exactly is the fact that the other democracies of the world did not choose to make the right to keep firearms in the house a constitutional right supposed to say about them?
well, you may not be a lawyer, but this is probably the most enlightening and insightful (not to mention most on-topic) comment in the entire thread. too bad we have to scroll through an entire page of fanboyish discussions to get to it :-)
Tip of the hat to you, sir.
Gotta love that link between the hardware limitations and the software concepts that may seem fancy but are essentially only built to get around them. I believe someone once called it "the law of leaky abstractions" - would be interesting to see what the new limitations would be if you start combining solid-state storage with pervasive multiprocessing, i.e. what can you do with a multi-processor multi-sdd server that you can not do with a single-processor single-hard drive server?
I think TFA is pretty right on the money that parallellization and massive use of SSD could cause some pretty fundamental changes in how we approach database optimization - if I were to imagine that rack that I'm staring at being filled with SSD drives and processors instead of with nothing but hard drives... locality of data takes on a whole new meaning if you don't require data to be on the same sector of the HD, but rather want certain sets of data to be stored on storage chips located around the same processor chips to avoid having to overload your busses.
Then again, I haven't been in this game for so long, so maybe I'm overestimating the impact. Oldtimer opinion would be very welcome.
... is 2 seconds too long.
Short answer: no.
Yes you can. Some examples: - replace "add 1024" with "substract -1024" - replace "if greater then 100" with "if greater then or equal to 99" - replace "copy a to b, copy c to d" by "copy c to d, copy a to b" Just have a look at any assembly language and use your imagination. To make matters even simpler, there are operators which completely ignore certain parameters (e.g. a JUMP operator which only takes 1 parameter leaves room for hidden data in the 2nd and 3rd operator field). There are plenty of instructions or combinations of instructions which leave room to such minor changes without any difference in execution. So for the steganographers, the goal would be to look for all of such instances in an executable, then agree on some kind of code (for example "add n" is a 1, "substract -n" is a 0). Semantically there is no difference, both codes will result in the exact same execution, but you found some wiggle room to leave a message. It was reported on Slashdot a few years ago.
Hmm,
just out of curiosity: what do you mean by open voting? Are you suggesting a system where the vote results are released in their entirety, with a one-way anonymization? So for example, i submit my vote via internet, it's registered and i get a message saying "your vote has been registered, your check number is 123456789", and then later they release the full list and i can go verify that 123456789 has indeed been counted as a vote for party X? Because I would consider that a very good system, but I've never heard anyone suggest it before... Are there known downsides to such a system?
The most obvious reason for me would seem to be simply avoid responsibility for the API until it is fully matured? Surely, if they were to release their API for the entire multi-touch aspect of the iPhone and iPod Touch at this point, they would be in a position where they have a lot of responsibilities:
* extensively documenting the API for a broad base instead of only for internal usage
* testing for possible bugs for usecases which are not relevant in Apple's internal usage
* making it feature complete
* making it secure
* when upgrading the API, supporting older applications built on that API (in other words, keeping full backwards compatibility)
All in all, this can be summed up as the basic fact that officially releasing the "mini OS X" that Apple uses on its portable devices as a development platform requires a whole different approach then simply using it themselves and not publishing it. All these responsibilities are easily avoided by simply not publishing the API and is a no-brainer if the company is on a tight deadline. Given the iPhone's short development lead time, i can fully understand that there was no time to get all of the above in order, so avoiding responsibility of the API for the time being seems like a logical thing to me.
That said, the above reason would steer them towards a tolerance stance regarding 'hackers', while Apple seems to be leaning more towards an 'active prosecution' stance, which i considere pretty much unjustified, together with the rest of the world.
Actually, that's what i thought at first as well - w00t, a full versioning file system in a mainstream os! But apparently, that's not quite it...
:-) . Finding info on large project servers and keeping track of different versions of the same files are two of the most common time-consuming problems I have encountered on virtually every project I ever worked on.
Time Machine simply does incremental back ups every night. It needs an external hard drive or a server to back up to. It's a backup utility, not a versioning file system.
Too bad, i kinda like where this was going: if they had gotten filesystem-level support for both versioning (Time Machine) & indexing (Spotlight) integrated with their X-SAN file system... every company in the world would want one of those babies
Enough said.
Actually, you haven't said quite enough yet. What counts for caching is not bandwith, it's latency, and you haven't said a thing about that. Try fetching a 100MB file of a tape streamer against fetching it off your HD, i'll bet the tapestreamer outperforms your HD in bandwith. Doesn't mean jack shit, though.
What makes the VM on a hard drive so shitty is the fact that the heads have to be repositioned for every read and that, because of that, it takes ages to read non-sequential data. RAM and flash memories don't have this problem. If the extra delay caused by the USB bus being between the flash drive and the system bus is minimal, the flash drive shout outperform the hard drive any day.
It also features such songs as "Honk if you want to plonk Zonk" "Post-it now, Post-it later" "Crap for Nerds, News for Turds!" and the epic poem "This Guy Has Got To Be The Worst Slashdot Editor In The History Of Mankind" I'll definitely go see it!
You mean, he bought himself _several_ Zens
only catches on when the porn industry starts supporting it. hmm... okay, maybe it's not their target audience
Just out of curiosity, are there any systems designed the other way around? I would think that making an OO design for the entire app, then letting a tool extract the structure for the database tables out of the classes would be a more logical approach then extracting the OO design out of the database tables?
So instead of "problems that have never been solved before", that should have been "users that have never been laid before" ?
While I agree it doesn't have to be music, the beeps kinda seem worse to me... one idea i really like is partylines. Basically, everybody who's on hold can talk to each other. I used to work at a radio station where some of our DJ's would have the partyline on speaker during songs, and sometimes they'd just throw people on the air if they were being funny. We once had six guys who were singing along to a song, on the air, without knowing it. Hilarious stuff. In tech support, it has some extra advantages. People could actually help each other out, if one has a problem that the other knows a solution to. Not sure if this would happen a lot in practice, but in theory it'd be nice...