|
This article is within the scope of the following WikiProjects: |
|
|
e · h · w · r To-do: |
|
|
-- moved to section in talk page --
- Rewrite the history section
- Ancient algorithms (Babylonians, Euclid, Sieve)
- Formalization -- done -- (Godel's and Herbrand's λ-calculus (cf footnote in Church's paper, p. 90 in Undecidable ), Church's theorem (1936) (p. 88ff in Undecidable), Post's "process" (1936) (p. 289ff in Undecidable), Turing's machine (1936-1937) (p. 116ff in Undecidable), J.B. Rosser's definition of "effective method" in terms of "a machine" (1939)(on p. 225-226 in Undecidable), Kleene proposing the "Church-Turing thesis" based on the papers of Church and Turing cited here (1943) (p. 273-274 in Undecidable)
|
Link to AllMathWords.org Encyclopedia.
I feel it is appropriate to include a link to http://www.allmathwords.org/algorithm.html in the Wikipedia article.
The Wikipedia guidelines state:
What should be linked
3. Sites that contain neutral and accurate material that cannot be integrated into the Wikipedia article due to copyright issues, amount of detail (such as professional athlete statistics, movie or television credits, interview transcripts, or online textbooks) or other reasons.
The reason the linked article should be perpemitted is that it is intended for a different audience that the Wikipedia article. The Wikipedia article is written at a college level. The All Math Words Encyclopedia is written for U.S. grades 7-10. The Wikipedia ariticle will be confusing to most 12-14 year olds. The All Math Words Encyclopedia article keeps the information and examples reachable by the target audience. —Preceding unsigned comment added by 76.27.81.30 (talk) 14:00, 5 October 2008 (UTC)
- I don't have a problem with the content of this link (altho it does refer, circularly, back to the wikipedia article). I would not have a problem with creating a sub-section of "References" with a title such as "For younger readers" and this link entered. Maybe Silly Rabbit would be willing to state its objections and its reversion. Bill Wvbailey (talk) 21:49, 5 October 2008 (UTC)
The subject is also covered in the Simple English Wikipedia. See here. pgr94 (talk) 16:30, 6 December 2008 (UTC)
- I was totally unaware of it. What a nice addition to wikipedia! Do you have an opinion about putting a link to this simple english version and/or to the All Math Words Encyclopedia? Bill Wvbailey (talk) 18:31, 7 December 2008 (UTC)
-
- I reverted the addition of the AllMathWords link because it appeared to be spammed across many articles in a short period of time, and the entries do not seem to provide a resource beyond that of a well-written article. (The link under discussion has virtually no content at all.) So I don't feel the link belongs here, but I'm not going to argue about it if you think it should be added back here. As for the simple English, note that there is already an interwiki. siℓℓy rabbit (talk) 18:57, 7 December 2008 (UTC)
Algorithm equivalence and normal forms
Is it possible to determine if two programs code for the same algorithm? For example, if an algorithm is expressed in two different languages can they be mapped back the same algorithm? More concretely, given implementations of quicksort in C, Java, Lisp and Prolog is it possible to determine (automatically) that the programs represent the same algorithm? This, I suppose, is the same as asking if there is a canonical form for expressing algorithms.
It seems like a fundamental question that I didn't see covered in the article. pgr94 (talk) 12:25, 26 October 2008 (UTC)
- A really interesting question. My guess is: formally, the matter is intractable in the same manner as the Busy beaver problem. But some thoughts: (I'm just a assembly-language coder (8085 and MC68HC), wrote a "universal program" for a home-built Post-Turing machine as well as a zillion little counter machine algorithms etc.) What I've observed is that the front-end "specification", if it is precise enough, usually sets up the task of "coding" which thereafter you just crank out. It is in the specification that we'd find the similarities -- the code will be unique for the instance but fall into a general classification or classifications. I'm thinking here of when I use a "state machine" design (but this devolves into the busy-beaver problem), for example, as opposed to "random code". Or a parsing table+indirect addressing rather than just a bunch of "case" tests (I've done both). This gets into the notion of a "toolbox" of generalized algorithms -- Knuth's cookbooks of algorithms, for example. There must be some oneone working on this sort of thing. The name E. J. McClusky at Stanford comes to mind. Bill Wvbailey (talk) 15:23, 26 October 2008 (UTC)
- There is a very general theorem, Rice's theorem, that says that there is no nontrivial property of a partial computable function, such that the set of programs that compute a function with that property is decidable. In particular, there is no way to decide in general if the function computed by a given program is equal to some predetermined function known in advance. — Carl (CBM · talk) 22:57, 26 October 2008 (UTC)
-
- Ok, the wording in Rice's theorem should talk about "the set of programs that compute a function with that property" rather than given/one (I reverted your last edit and it looks like you are the person to write better wording). Derek farn (talk) 01:36, 27 October 2008 (UTC)
- Correct me if I'm wrong, but Rice's theorem doesn't rule out the use of "heuristics" on specific instances of programs; Rice's theorem has to do with a generalized mechanical procedure extended to all possible programs-as-inputs. It would be quite possible for a Carnivore-like monster program to crunch through an instance of "a program" looking for "pattern matches", perhaps simulating it; sometimes it would succeed, sometimes not, and if not it would "time out." All of these programs are finite in nature, and their inputs are finite as well -- so they are finite state machines and hence theoretically "tractable", but in practicality "intractable" in the sense of the busy beaver problem. Rice's theorem is really only applicable to a infinite-tape Turing machine . . . isn't this correct? Bill Wvbailey (talk) 14:42, 27 October 2008 (UTC)
-
- You're morally right, but that solution is very impractical. If you specify a fixed finite amount of memory that the program in question can work with, then it is possible to analyze a program by "brute force", testing its execution on every possible input as if it were a finite state machine. Then you could assign the program a standard form as some other finite state machine. However, you can't do the analysis via any method that does not make use of an assumption of a fixed memory bound, because any general method would also apply in the case of unlimited memory, which is what Rice's theorem prevents. So apart from some limited heuristics, the "normal form" would not be obtained by direct syntactic manipulation of the original program; it would just be some more-or-less arbitrarily selected program that happens to have the same behavior.
-
- For a quantitative estimate, suppose that the program takes a single 32 bit integer as input and uses no other external state information at all. Then there are 2^32 instances of the program that have to be brute-force tested in order to create a normal form. That would take about 50 days to do at 1000 instances/second. If there is any other external information that the program uses that could change, you have to run all those possibilities as well, which would increase the number of possibilities exponentially. — Carl (CBM · talk) 15:15, 27 October 2008 (UTC)
I'm not familiar with Rice's theorem and it does appear very general. Google led me to this article doi:10.1016/j.tcs.2006.07.021 which strikes me as quite relevant:
- Prime normal form and equivalence of simple grammars
- A prefix-free language is prime if it cannot be decomposed into a concatenation of two prefix-free languages. We show that we can check in polynomial time if a language generated by a simple context-free grammar is prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into prime normal form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve the complexity of testing the equivalence of simple grammars. The best previously known algorithm for this problem worked in O(n13) time. We improve it to View the MathML source and View the MathML source time, where n is the total size of the grammars involved, and v is the length of a shortest string derivable from a nonterminal, maximized over all nonterminals.
If we can establish a normal form for context-free grammars then wouldn't it suggest Rice's theorem is not a problem? pgr94 (talk) 15:59, 12 November 2008 (UTC)
- Context-free languages are only a small subset of all decidable languages. So even if there is a normal form for context-free grammars, this does not imply a normal form for arbitrary grammars. — Carl (CBM · talk) 17:54, 12 November 2008 (UTC)
- True, but aren't context-free grammars a good start: "Context free languages are the theoretical basis for the syntax of most programming languages."[1] pgr94 (talk) 18:17, 12 November 2008 (UTC)
- Yes, they are a good start. — Carl (CBM · talk) 03:05, 13 November 2008 (UTC)
|
This article has an assessment summary page.
To-do: