Prev: Check out POASM
Next: Bad habits
From: randyhyde@earthlink.net on 30 Jan 2006 18:36 Charles A. Crayne wrote: > On 30 Jan 2006 08:59:41 -0800 > "randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> wrote: > > :Chuck, how much time have you put into studying this problem? > > In the generic sense, I have been working with this problem for about > forty years professionally, and for about 30 years with my own hobby > systems. Uh, and you accuse *me* of saying "believe me because I'm saying it"? You're about a decade ahead of me professionally, but the big difference between us is that I've written several compilers and assemblers and I've *researched* this problem enough to know that it doesn't have a trivial (or even easy) solution. It's not quite insolvable, but it's not a practical problem to solve. You can put in a lot of work and get an 80% solution (or the amount of work Rene is thinking about and get a 20% solution) and then it's going to break on a lot of code that the average user writes. All this work for the four or five people who might actually make use of the tool? Hmm.... Cheers, Randy Hyde
From: randyhyde@earthlink.net on 30 Jan 2006 18:39 Betov wrote: > > Though, these would also be good subjects for books: > > * "How to publish books when you are a definitive nerd" > - In ten lessons, by a professional nerd, for hobbists nerds -. Do you think you are insulting me by calling me a "nerd"? Sorry dude, I wear that badge with pride. I'd gladly put it on a book because that title will sell even more of them. Haven't you heard? It's been cool to be a "nerd" or a "geek" in this business for quite some time. Cheers, Randy Hyde
From: Robert Redelmeier on 30 Jan 2006 19:21 randyhyde(a)earthlink.net <randyhyde(a)earthlink.net> wrote in part: > No, the *problems* are not solved. Instead, people settle > for a solution to a different problem. For example, a greedy > algorithm implementation of the travelling salesman problem > may produce an okay result, but it is *not* a solution to > original problem. It may be "good enough" for government > work, but it is not the solution to the original problem. That depends on your definition of "solved". If you don't insist on a perfect solutions, many are available. -- Robert
From: Robert Redelmeier on 30 Jan 2006 19:40 Alex McDonald <alex_mcd(a)btopenworld.com> wrote in part: > I think you've cheated here! You said "theoretically insoluble". Perhaps. What I meant was more like "theoretically extremely difficult to solve". > I wouldn't say busy beaver's been "practically solved" at all; > it's not that kind of problem (and yes, it's theoretically > insoluble). If you've got a definition of what constitutes a > practical solution for busy beaver, I'd like to see it. Sure it has. AFAIK, all solutions have been trial-and-error. Not elegant, but eminently practical: http://www.drb.insel.de/~heiner/BB/ > As to travelling salesman problems, there's no efficient > way of solving them for large n. You can get what appear > to be good solutions for large n in reasonable times, but > you don't know how far from optimal they are. Of course, > the easiest solution is just to label the cities 1 through > n and visit them in that order. Practical its not! Certainly it's practical. Anyone can do it. It's just neither efficient nor elegant. > "The halting problem also solves" I didn't understand... What > does it solve? Sorry. I meant the halting problem is also usually solved. Less relibably on Microsoft software, ( which sometimes doesn't). -- Robert
From: randyhyde@earthlink.net on 30 Jan 2006 19:46
Robert Redelmeier wrote: > > That depends on your definition of "solved". If you don't > insist on a perfect solutions, many are available. > Then they are different problems. The Travelling Salesman problem is *quite* specific, for example. Compute a guaranteed minimum path between the nodes in a graph, with each node being visited exactly once. If you don't require the minimum path, or you allow nodes to be visited more than once, you can devise a tractible solution, but it is a solution to a different problem. Rene may think that he has "solved" the disassembler problem, for example. He's basically announced that the project is complete, even though it is *far* from suitable. Just because he's tired of working on the project doesn't mean that he has "solved" the original problem. Ditto to the code conversion problem. As I've said many times already in this thread, Rene (or whomever) is free to redefine the problem in order to make it easy to solve. But the results may be of little practical use. As for insisting on perfect solutions, sometimes you can't. Perfect (automatic) disassembly, for example, is impossible. We have no choice to accept something less than perfect if we want to use a disassembler. Because disassembly is undecideable, the only realistic solution is to create an interactive tool that allows the end-user to guide the disassembly process, so as to create a reasonable facsimile of the original program. This can be a lot of work on the end-user's part, but there is no alternative. The code conversion problem is quite a different animal. It *is* possible to write such a program, even a perfect one, but the solution may not be practical for a different reason -- to create a semantically correct equivalent of the x86 on another processor may wind up producing code that is *horribly* inefficient. Especially if you don't follow up the code with an optimizing that does a great job of eliminate dead instruction sequences (based on data flow analysis of the source code). Of course, the above paragraph assumes that the author of the tool *really* knows what they are doing (and I will freely admit that I've not studied the problem in sufficient detail to claim I know *everything* that has to be done -- I've only studied it in enough detail to know that it's going to take a lot more work than I'm willing to put into it). The suggestions being made around here and the comments about the conversion program suggest that people making the claims about the possibility of a program would write code that doesn't come close to correctly compiling x86 code to some other processor. Oh, their ideas would make for some great demo programs, but much like Rene's little disassembler, when you try to use such a tool for real work, it will break consistently. Going back and manually fixing all the bad code, as Chuck suggests, just isn't an option. It will be far easier just to rewrite the code from scratch. Better yet, it's far easier to use a HLL if you really need portability to a different processor. Cheers, Randy Hyde |