Release of RosAsm V.2.025a
in [ASM]
|
From: Beth on 2 Oct 2005 21:21 Randy wrote: > there is not a > one-to-one mapping of programs to binary object files, this is why it's > fair to say that writing a perfect disassembler is an impossibility. Excellent! How many different ways can the same point be proved over and over before some people cotton on? For those who haven't thought what point Randy is making: If there's not a 1:1 between program and binary then more than program can produce the same binary...how can a "perfect disassembler" use _ONLY_ the information in the binary to differentiate between the many possible programs that could produce the same binary? I explained this to you before, wolfgang..."entropy"..."information loss"...it might not be aesthetically pleasing to the "symmetrical" sense humans tend to have but some things simply are not reversible...we're talking about an entropic process... You can take a china plate and throw it to the ground to smash it into a million pieces...but you won't find any million pieces of china plate jumping up off the ground to form the original perfect plate again... And if you think "I'll just use superglue to piece it back together"...one, you're "external" so that's kind of cheating...and, two, you still can't get the plate back perfectly to its _EXACT_ original state (minus superglue, minus cracks and other imperfections it gained when it smashed and cannot be "undone")... "Entropy"... As the First Law (of Thermodynamics) tells us: "you can't win"...and the Second Law rubs it in just to be cruel: "you can't break even" ;) Beth :)
From: Beth on 2 Oct 2005 21:21 Charles A. Crayne wrote: > Randy wrote: > :If you take *all* the possible bits in a > :hypothetically maxed-out x86 system (including all secondary storage, > :registers, memory, and anything else that can be set one way or the > :other) > > Using your definition, not only is the number of machine states > inconceivably large, it is also indeterminate, and varies over > time. > > For example, my machine, like many others, has a full-time Internet > connection. In theory, every machine state in every every machine which is > also connected, or which could possibly be connected, to the Internet could > be affected by a program on my machine. > > In addition, my machine, like most others, has removable media, and during > the execution of any given program, could have an indefinite number of > media swaps over the lifetime of a given program. > > Finally, my machine, line a number of others, has programs which run for a > month or more. Since I can upgrade my machine with additional resources > while these programs are running, the total number of machine states may > grow over the lifetime of a given program, from this cause, as well. Exactly!!! Now take all those possible states that are now even more stupidly large by orders of magnitude in this "machine" you're talking about and place it on a "two to the power of" calculation... 10^78 elementary particles in the universe... "Do the math", as you Americans like to say ;)... You further assist in proving the inherent impossibility of it all...thank you :) Beth :)
From: Beth on 2 Oct 2005 21:56 Charles A. Crayne wrote: > To begin with, I can easily design an 'x86-like' architecture such that, > for all possible programs which run on that architecture, it is trivial to > determine if the program halts. Are you sure? Does your x86-like CPU have any external interrupts? Is it capable of generating exceptions (self-interrupts, so to speak) that are variable on an external stimulus of some kind (which includes a real-time clock, as well as the more obvious input devices)? Can you determine that no possible combinations of "machine state" and all "external states" that can effect the machine's state that there is no possible combination that could generate either "deadlock", "livelock" or logically inescapable "starvation"? All states which prevent the program reaching a halt? If the program to be tested does not correctly employ solid synchronisation in a pre-emptive concurrent environment then how can you determine that which is logically "indeterminable" and "non-deterministic"? Consider a program which suffers the "multiple update" problem...there is a global variable shared by multiple threads...each of which are scheduled pre-emptively (which is interrupted dependent on a real-world clock, as per usual) to increment the global variable _WITHOUT_ employing safe synchronisation between the threads (that is, it is capable of suffering the "multiple update" problem)...I have posted up exactly such a program before to make this same point to hutch... Logically, the final state of this program is inherently "indeterminable"...how do you propose to determine that which, logically, is "indeterminable"? A variation of "chaos theory", if you will... Scheduling the threads impacts the final result of the global variable (because it will "multiple update" whenever a thread is interrupted mid-increment by another thread...and the global variable will "skip a heartbeat" and register one less than what it should register)... The scheduling is itself dependent on a real-world time interrupt signal (e.g. the scheduler sits on the end of an external timer interrupt...real-world time itself is an "external" entity out of the CPU's control in this instance)... Instructions take time to complete...the time they take depends on a myriad of factors from the cache state (which itself logically "echoes" because the cache effects the timing, the timing effects the scheduling which, in turn, comes back to effect the cache...it's a singular _SHARED_ resource in a concurrent environment, you see :)...page faults, disk swapping, a movement of the mouse triggering an interrupt, connection of a USB device, arbitrary internet "stay awake" signal just happens to come over the connection at the "wrong millisecond"...even the temperature of the room, the imperfections in the materials, etc., etc....all can conspire to alter the "timing"...the scheduler runs on a real-world timer interrupt...where the scheduler interrupts the threads - down to the individual instructions - effects whether "multiple update" happens or not... It's just like the butterfly and the tornado that you've probably heard about to popularly explain "chaos theory"...we've got at the very least two interacting independent systems...the CPU's operation and "time" itself...as in real-world time, as in the abstract concept, as in "spacetime continuum"...oh, wait, that's another factor I forgot to include!!! Relativity...if the machine is on a rocket travelling at near light speed, makes a round trip and comes back to a human being on planet Earth who did not journey on the rocket then their "local frames of reference" would be different due to relativity, which effects when they might move the mouse, which effects the "timing", which effects at which exact instruction the scheduler interrupts the program, which conspires to make the pre-determination of when and where "multiple update" will occur impossible...that's chaos theory for you...doesn't even need to go on a rocket - that just exaggerates relativity to significant and measurable levels - if it moves in any way whatsoever then on an immeasurably small scale, it is travelling through time as well as space (Einstein's "spacetime" stuff: Time and space are not independent that movement through one is movement through the other, like it or not)... Such a program - by "chaos theory" - has an inherently "indeterminable" final state...because that state depends on a myriad of independent and external factors, where even the smallest "flap" of the butterfly's wings _CAN_ produce a "large scale effect" equivalent to the proverbial "tornado" in the final state of the program... Ah, but we can simply measure the real-world timings, right? Equally not logically possible for the CPU to do this to itself...a touch of Godel (a closed system cannot fully comprehend itself without reference to an external entity) and a touch of "Schroedinger's Cat" (the observation itself changes that which is observed)... For example, you might think we can use "RDTSC" to measure the exact clock cycles and cache use and such perfectly...unfortunately, "RDTSC" _TAKES TIME_ to do its stuff...the observation itself effects what's observed...you run "RDTSC" and this changes the timing itself because "RDTSC" needs to run...the instruction changes the very observation it's trying to make into the "timing" of the program to exactly measure the chaotic "scheduling" issue we need to know _PRECISELY_ (down to the "butterfly wing" level)...otherwise, our program is "indeterminable" due to chaotic effects on the scheduling of threads... This brings in Godel...this system cannot precisely measure itself without reference to an external source (you could measure the cache and other factors involved with external meters or another machine hooked up to it that can "RDTSC" without actually effecting the operation of the program itself)... Requiring this "external source" to overcome "chaotic influence" (where "the observation itself effects what's observed" that the "closed system cannot comprehend itself without external reference") can potentially solve this logical problem... _BUT_ it's screwed up your "I can design an x86-like system that's determinable" claim...no, you can't...you must have that "external reference", sorry (Godel)...as the "closed system" cannot precisely measure itself to the required level (Godel) in order to accurately 100% determine the "timing" of the program (Chaos)...if that cannot be determined with a program who's termination (final state) is dependent upon it...to determine whether it does or doesn't encounter "deadlock", "livelock", "starvation" or other erroneous concurrent execution states that _PREVENT THE PROGRAM REACHING A HALT_...then you logically cannot create a system where you can guarantee, for all possible programs, that you can always determine its final state... I've openly and explicitly given you all the necessary logic to see this conclusion for yourself...feel free to follow it and show me where there's any flaw in the logic, if such does exist... What Randy has said about the Halting Problem has a direct effect on "concurrent theory" (in different form as mentioned above), where it is also known categorically and indisputably that a concurrent program's "partial ordering" under a scheduling system that introduces dependencies on real-world time (which the pre-emptive fair scheduling that nearly every multi-tasking system out there fully qualifies as being) is inherently (due to the "chaotic influence" I've just explicitly taken you through the logic of) "non-deterministic"... And, of course, what "non-deterministic" means is exactly contradictory to the claim of full and accurate "pre-determination" of the program's final state... It's basically the same result known in concurrent theory but under a different guise (this is where, in practical terms, the result known from "the Halting Problem" ceases to be a theoretical point and actually is a very real practical point for constructing concurrent applications that don't fall foul of failing to properly "synchronise"...or, indeed, you end up with "non-determinism" and usually, for most programs, that's a _BUG_ and you don't want it to be "non-deterministic"...to avoid that problem, this is why a proper understanding of things like "mutexs", "deadlock conditions", "synchronisation primitives" really _ISN'T_ "optional" knowledge for the construction of concurrent applications...that's what I was trying to tell hutch before when he thought it "didn't matter" and that writing multi-threaded applications was "like DOS batch programming but, like, more than one thing happens at a time"...no, sorry..."parallelism" is a _LOT_ more complicated than that...I've given you the logic to follow for yourself to see this, Hopefully...but I would also draw your attention to another fact that I've mentioned before that I did research work on neural networks...which operate in a major way on the concept and differences "immense parallelism" makes...they are _NOT_ the same as a sequential system "but more is going on"...they have inherently _DIFFERENT_ operational properties...in fact, a neural network (which includes the one stuck between your ears because that's how your brain operates too) gains its "intelligence" by that very "immense parallelism"...the actual "neurons" in a typical network are exceedingly dumb (in animal brains, they are also often slow-operating because chemical reactions are partially involved)...but it manages the incredible - fundamentally and logically _DIFFERENT_ - property of "intelligent" behaviour almost exclusively from the _PARALLELISM_...not from complex operation... I tried to get this over to hutch but he just wasn't prepared to listen...parallel is an entirely different kettle of fish - different properties, different techniques, etc. - to sequential operation... If we were talking something entirely 100% sequential then you might have a point...but concurrency (and note that even DOS is capable of a strange kind of concurrency when external interrupts are triggered...a CPU can interrupt its own operation that even a system you might think is "sequential" technically isn't :) can produce "non-deterministic" results...that is, indeed, totally and utterly unheard of...a total alien concept...a program that does the same thing every time it's run but produces different results (even when, yes, working from the same "input file", if the programmer screwed up handling the "synchronisation" properly)... Many programs crash and are inherently buggy because far too few programmers properly understand these issues and concepts...indeed, it's probably safe to say that many programmers don't even realise that there are "issues" to be dealt with at all (witness hutch's program and his firm belief over and over again that his approach is perfectly valid)... Beth :)
From: Charles A. Crayne on 2 Oct 2005 23:00 On Mon, 03 Oct 2005 01:56:27 GMT "Beth" <BethStone21(a)hotmail.NOSPICEDHAM.com> wrote: :Are you sure? Yes! :Does your x86-like CPU have any external interrupts? Yes. :Is it capable of generating exceptions (self-interrupts, so to speak) :that are variable on an external stimulus of some kind (which includes a :real-time clock, as well as the more obvious input devices)? Yes. :Can you determine that no possible combinations of "machine state" and :all "external states" that can effect the machine's state that there is :no possible combination that could generate either "deadlock", :"livelock" or logically inescapable "starvation"? All states which :prevent the program reaching a halt? If the program continues to receive cpu cycles, it will behave as I stated. On the other hand, if you consider the total destruction of the universe as merely another external interrupt, then all bets are off. :If the program to be tested does not correctly employ solid :synchronisation in a pre-emptive concurrent environment then how can you :determine that which is logically "indeterminable" and :"non-deterministic"? I am not proposing to 'unscrew the unscrutable', but rather am showing proof that on such an architecture the halting problem is easily determined. :Consider a program which suffers the "multiple update" problem...there :is a global variable shared by multiple threads...each of which are :scheduled pre-emptively (which is interrupted dependent on a real-world :clock, as per usual) to increment the global variable _WITHOUT_ :employing safe synchronisation between the threads (that is, it is :capable of suffering the "multiple update" problem)...I have posted up :exactly such a program before to make this same point to hutch... OK, I have considered it. :Logically, the final state of this program is inherently :"indeterminable"...how do you propose to determine that which, :logically, is "indeterminable"? I do not claim to predict the final state of the program, but only that the program will eventually halt. If you need any more clues, feel free to ask. -- Chuck
From: T.M. Sommers on 2 Oct 2005 23:24
Jim Carlock wrote: > <randyhyde(a)earthlink.net> wrote: > >>If you take *all* the possible bits in a hypothetically maxed-out >>x86 system (including all secondary storage, registers, memory, >>and anything else that can be set one way or the other), then >>one configuration (that is, bit pattern) of all these bits is *one* >>state of the machine. Now raise two to the power specified by >>this number of bits and that the number of possible states in the >>system. This is a *very* large number. > > That's like stating calculating the temperature is NEVER exact, > because an infinite number of temperatures exist for each and > every molecule within a substrate and each every molecule > travels at a different speed, and each operates at a different > temperature while the states constantly change. Huh? Temperature is a macroscopic property of systems of particles, not a property of individual particles. Temperature is by definition the reciprocal of the partial derivative of entropy with respect to energy. It makes no sense at all to say that an individual particle has an infinite number of temperatures. -- Thomas M. Sommers -- tms(a)nj.net -- AB2SB |