Talk:Recursion theory

From Wikipedia, the free encyclopedia

Contents 1 Rewrite of 2006-6-27 2 An opportunity?: Can we use small computing machines to demonstrate partial recursion, general recursion, etc? But first: What are all these different types of recursion? 3 Table from Soare (1995) 4 A tiny quibble: re Generalizations of Turing computability 5 A scan of the article

[edit] Rewrite of 2006-6-27

I significantly expanded the previous article. It still needs a lot of work.

• The relationship to proof theory needs to be made more explicit
• The History and Scope section is not complete
• The references should be expanded

Because this article doesn't need to contain any technical details, there is no reason why it should not be completely accessible to the general educated audience. CMummert 14:09, 27 June 2006 (UTC)

[edit] An opportunity?: Can we use small computing machines to demonstrate partial recursion, general recursion, etc? But first: What are all these different types of recursion?

wvbailey here: My questions:

(1) Can we concoct a way to describe "recursion" in terms of "simple machine" models such as Post-Turing, register or random-access machine models?

(2) partial versus general recursion versus primitive recursion (or whatever) -- a simple explanation? see below re Davis (1967)

Here's why I ask:

I ran into an interesting quote + derivations in a paper: Calvin C. Elgot and Abraham Robinson (1964), Random-Access Stored-Program machines, An Approach to Programming Languages, JACM Vol. 11, No. 4 (October, 1964) pp. 365-399.

This (for me) is a difficult paper. But I have a suspicion that, for some of us non-mathematicians, this recursion stuff wouldn't be so abstract if we could translate it into the action of little machines, or little models of humans-as-machines doing 'recursion' on ruled paper as if we were machines.

In fact Elgot-Robinson do this, but as I say their paper is not so easy. (In the following, "x" is a "memory register" (i.e. a place in space) in their Random Access Stored Program "RASP" computer-model, and ^2 references Davis (1958) Computability and Unsolvability). They state that:

 :The class of partial recursive functions is the smallest class of functions closed under composition and minimalization [^2, p. 41] containing

1. "the constant function c₀(x), c₀(x) = 0
2. "the successor function S, S(x) = x+1
3. "the projection functions U_iⁿ, U_iⁿ(x₀, ... _n-1) = x_i, 0 ≤ i < n,
4. "addition,
5. "proper subtraction (x ┴ y = 0 if x ≤ y, x ┴ y = x - y if x ≥ y)
6. "multiplication" (pp. 379ff)

Question: Can "composition" and "minimalization" be explained in layman's terms? Examples?

They start with their greatly-reduced model of a "stored program machine" (i.e. program is together with the data in the common "register-space" like a universal Turing machine). The model includes:

1. successor S(x): Add one to the contents of register x, then continue with the next instruction in sequence
2. copy D(x, y), i.e. copy the contents of register x to register y & leave contents of x changed, then continue with the next instruction in sequence
3. conditional transfer on equality C(x, y, z), IF the contents of register x equals the contents of register y THEN fetch the next instruction from register z, ELSE continue with the next instruction in sequence.

And from these they show how (in this order) to:

1. create the projection function
2. create the equality relation
3. do addition of natural numbers
4. do multiplication of natural numbers
5. create the binary relation ≤
6. do proper subtraction

I find this fascinating. That everything that is computable in all of mathematics can [hypothetically] be done by the above 6 arithmetic operations "with composition and minimization (whatever that is), and these can in turn be done by 3 machine instructions operating in/on a "register space" (a sequence of numbered boxes into which we can write numbers and then change them per a list of instructions). [Is this a true statement? Is there a simpler set rather than 6? But what then is 'full general recursion' -- is it it more "powerful" than partial recursion? etc]

(2) Minsky: Then there's an interesting tidbit in Minsky (1967). Instead of using RASP models he uses "register models". (He calls them "program machines" but I find his choice of name unfortunate. With the register models it is very difficult to include the program in the registers, for instance.). He claims almost the same three simple instructions (he uses inequality rather than equality and concots some other similar trios). Minksy then "demonstrates" that a set of the three instructions { "set a register's contents to 0" [0], "successor function" ['], "IF register's contents = 0 then jump else decrement" [-] } "is equivalent to" (p. 208) the "general-recursive" functions. To do this he first creates "copy" and "jump unless equal".

There's more: he also creates a set of instructions and shows that they are equivalent to the primitive recursive functions. This set includes a "repeat instruction" [RPT]. But he observes that one kind of [RPT] computes the "partial recursive functions" while the other creates the "full recursive functions". This has to do with whether or not the "repeat" command [RPT] includes or does not include itself 'in its range' <= huh? Does this have to do with self-modifying instructions?

So I ask: in layman's terms, what is the difference between all these kinds of recursion?

1. Partial recursion
2. Full general recursion
3. Primitive recursion

And what is 'the minimization operator' that Elgot-Robinson and Minsky mention? Is this necessary for "full general recursion"?

Is there a way to use these machine-models to form "demonstrations" that are more 'concrete' -- less abstract, more constructive -- than pure "recursion theory" (which I find utterly opaque -- just masses of subscripts). For example:

I always think of "partial recursion" and "lambda calculus" as something done by hand on paper by mathematicians, not done by machines. Is this a correct statement?

Is there somewhere an example of multiplication done by recursion theory? Does this question even make sense?

All the machine models divide the machine into "instructions" contained a finite state machine (FSM) and "the machine memory". Sometimes, as in a Universal Turing machine and the RASP model, the data-memory also contains the instructions (but in the RAM and the register-machine models the instructions and data-memory are separate). In the UTM and RASP cases there's still a core FSM that interprets the "instructions-in-memory". Is there something equivalent to this FSM in recursion theory? (e.g. the mathematican's brain?) Just where do "the instructions" reside?

Examples would provide a nice tie-in with Register machine and Random access machine models, if a person can figure out how to do it so it isn't too abstract. As I look back, I realize that I could include some of the above in both articles, but I have to feel more confident that I know what I'm talking about with regards to recursion (I sure don't have that confidence now) [I really need to see an example of "multiply" that would help alot]. That would leave "lambda calculus" to be tackled (I know squat about that -- ditto for an example of "multiply") but then we would have the historical elements behind the Church-Turing thesis (more or less) covered.

wvbaileyWvbailey

This article is still pretty high-level. To make it more accessible to the general public, one thing that needs to be added is an explict explanation the the field recursion theory was named for recursively defined functions but this formalization is not often used in contemporary research. The origins of the name are well explored by Soare's 1996 paper [1] which is already a reference in the article. I recommend that article for a thorough overview of the history of the word recursive.

Moreover, the field of recursion theory has distanced itself from the use of specific models of computation. Some formal model is often used to define the computable functions, but this is not necessary as they can be defined using the arithmetical hierarchy or inductively defined as a class of functions in various ways. In any event, once the existence of an enumeration of the partial computable functions has been established, this enumeration is then used so that no additional reference to the model of computation is required (this goes back at least as far as Rogers' book). Thus a detailed description of various models of computation is not apropos here, although links are good. Also, the field of recursion theory includes topics such as hyperarithmetical theory that study models of computation that are not Turing computable at all.

My hope is to get this article to the point where it can be peer reviewed and, I hope, become a good article. To achieve that, I think that the article should focus on a nontechnical introduction to the field. CMummert 00:08, 18 September 2006 (UTC)

Well, there's kind of an elephant in the room. It was my fault that this article was forked from computability theory (computer science). I really think the articles should be re-merged, but with the existing material at computability theory (computer science) edited to make it substantially shorter. Some of the material is probably duplicative of existing articles, and if it's not, then the more detailed parts can go to one or more new articles. But there ought to be one survey article of the entire field, and it needs to move along a bit faster than the existing CT(CS) article. Simply merging the existing recursion theory into that article is not a good option, because the interesting stuff would not show up until too late in the article. --Trovatore 06:09, 18 September 2006 (UTC)

One problem I see with merging is that the CS article is important to computer scientists, so any merging and cutting of "their" ariticle would have to be done with great care. I don't have the energy to coordinate so much with the computer science project, so I thought the slight duplication between articles was acceptable. The CS side has Theory of computation as their main article, which says that "theory of computation" splits into computability theory and complexity theory. I am not sure whether this is standard terminology or not. Would we merge Recursion theory into computability theory or into theory of computation? CMummert 10:30, 18 September 2006 (UTC)

[edit] Table from Soare (1995)

Soare's survey (p. 29) is very useful for showing language used. But before using it "relative computability" needs to be defined. And the purpose of the last column is not clear. Whether something such as this should go here or in the computability theory or both, I am unsure. The table does provide a nice tie between the two theories.

Book	Definition of computable	Definition of relative computability	Name used for function defined
Kleene 1952	general recursive	general recursive	recursive
Rogers 1967	Turing machines	Turing machines	recursive
Cutland 1980	register machines	register machines	computable
Lerman 1983	μ-recursive	Turing machines	recursive
Soare 1987	Turing machines	Turing machines	recursive
Odifreddi 1989	μ-recursive	μ-recursive	recursive
Shoenfield 1991	register machines	register machines	recursive

A proviso: Soare's meaning of "register machine" needs to be looked at more closely (i.e. I will need to check all his references). A register machine provided with "indirect addressing" (e.g. Melzak's 1961 holes-and-pebbles model, models of Cook and Reckhow 1973) is really a "random access machine" (RAM) -- and I have not seen a user-friendly way to convert a register machine into a RAM. The most primitive register machines (e.g. Minsky 1961, 1967) with only 1 or two tapes require fussy encoding (Godelizing, factorization of a huge number on the tape). RAMS, on the other hand, are very easy to use, as they resemble ultra-primitive RISC processors with Harvard architecture. wvbaileyWvbailey 14:21, 29 September 2006 (UTC)

There is no difference between computability theory and recursion theory; they are synonyms. They refer to the study of computable and relatively computable functions. While a model of computation may be used to define these functions, the specific model of computation is not particularly important. A contemporary research paper is unlikely to mention any specific model of computation whatsoever.

Relative computability. If a set A is computable by an oracle Turing machine using oracle B then A is relatively computable from B. Similar, and equivalent, definitions can be given in terms of other models of computation. Or in terms of the arithmetical hierarchy: A is relatively computable from B if A is definable.

When Soare says register machine he probably means a machine that has registers and no tapes. This is now standard terminology. I think you are attaching too much weight to old sources, such as Minsky, which use terminology in ways that are no longer standard. The most widely used contemporary introduction to computability theory is Soare's book. Soare is working on a revised version which will likely be the next golden standard reference.

I've taken more of a survey approach with the wiki-articles I'm slogging away on. Actually, through my ancient-history background searches I derived virtually the identical machine hierarchy as that in a survey article by van Emde Boas (1990) pp.3-66 with 141 references (!) in Handbook of Theoretical Computer Science, Volume A: Algorithms & Complexity QA76.H279 1990. (A very useful source comparing results of complexity theory measures between the various models (multitape-TM, register machine, random access machine (RAM), random access stored program machine (RASP), & pointer machine). Our definitions agree with one exception: he gathers the RAM and RASP into the general category "register machines" and I've broken them out/away from the classical "register machine": Thus a RAM is a register machine with additional indirection (van Emde Boas agrees, p. 23), RASP is a RAM with a program in its registers (van Emde Boas agrees, p. 24). Maybe this is where the terminology confusion comes in. It will be good to check Soare and update my Turing machine equivalents work. That whole page will get a rework at some point.

This is as much a reminder to myself as a clarification to others: the article register machine presently uses the names "counter machine" and "register machine" synonymously. Perhaps "register machine" should reserved for a class of machines including { counter machine, RAM, RASP machine, pointer machine }. The "counter machine" would remain as described in the "register machine article" -- a very primitive device indeed. Maybe Soare gives guidance too. But I need support from the literature. wvbaileyWvbailey 20:57, 29 September 2006 (UTC)

Are there are too many new books? Every author comes from his own angle/viewpoint with his own pet model (e.g. Davis-Sigal-Weyuker (1994) use a single-tape, multi-symbol Post-Turing machine model). Different model-usage seems to have to do with 'computing on strings' versus 'computing on numbers'. van Emde Boas actually gives a bunch of sub-names to RAM models on his page 24. As I recall I referenced these in the Turing machine equivalents (so many articles, so few brain cells...)

I hope Soare is doing good: a new presentation isn't necessarily a good one, or an improvement. Case in point; my thermodynamics text was written by the prof I had at the time and who was the dean of the school to boot -- Myron Tribus -- just a horrid text! Just horrid... I was in trouble, failing the tests. So I went deep into the stacks, got out the original thermo text by the original author (can't remember name) ca 1850's (a musty, smelling thing it was) ... and suddenly Carnot cycles etc. became clear as a bell. And there was Linville (chair of EE at Stanford at that time) who required everyone in the dept. to take his course we derisively called "Linville's Lumpenses" -- his "lumps" were never to be seen in the literature again (nigh 30 years anyway) and utterly useless. What a waste.

Poor students ... they need all the help they can get. In the article register machine I used extensively the same source Soare references (p. 17)-- Shepherdson-Sturgis (1963). It was suggested to me by a reader who wondered why S-S weren't mentioned in the article, why "register machines" are called "Minsky machines", for instance. So I did the ancient-history search. (An interesting read, actually about the collision of papers by Minsky, Lambek and Melzak and Shepherdson-Sturgis all in 1961 but S-S didn't appear until 1963. It turns out the Germans were there first (mid '50's, notably Rosza Péter.) Soare's set of register-machine instructions (in his paper) is just another version that is not always used -- the Peano axioms in disguise. But Soare augmented them with "transfer" -- a very useful instruction indeed.

Anyway until I see his treatment I don't know how "easy" it is for Soare to show that the register machine without "indirection" is Turing-equivalent. The clumsy 2-tape factorization method used by Minsky is why Malzek (1961) added indirection (indexing) to his model to make it into a RAM random access machine. Then a demo becomes very easy. (I'll bet Soare does the same thing ... but we shall see...). I will explore Soare next time I get to the library.

Thanks for your briefing on this stuff. (I would love to see papers by Rosza Péter , Horst Kaphengst, and H. Hemes referenced in Shepherdson-Sturgis but so far I haven't found them in the Dartmouth library, and I can't read German anyway. Any thoughts? Thanks ...) wvbaileyWvbailey 18:38, 29 September 2006 (UTC)

This article could use an explanation (very brief) of what Turing computability is, before the terminology section. I'll try to write it soon. CMummert 14:44, 29 September 2006 (UTC)

By the way, I just got a chacne to look at the textbook Automata and Computability by Kozen. It's organized as a series of lectures and seems very clear to me. It is focused on computer science, but I think that the part from Lecture 28 to the end gives a nice overview of recursion theory and its relationship to Godel's incompleteness theorem. In particular, it explains several models of computation including μ reccursive functions, Turing machines, and λ calculus. CMummert 17:09, 29 September 2006 (UTC)

When I said that Soare's Computably enumerable sets and degrees is the standard reference, I mean the standard reference that a research paper would cite as a reference on basic concepts. It is a graduate-level book; the improved presentation is really intended for clearly explaining topics that are generally considered technical, such as difficult priority arguments, rather than giving a leisurely introduction to the basic facts about Turing computability.

I have looked at very few undergraduate computability theory books; in my impression they tend to either

• Be computer science oriented, with an emphasis on formal languages and automata. This is very important for computer scientists, because automata are used in the specification of compiler algorithms and network protocols, and you can't understand computer science without understanding them.
• Or be general introductions to mathematical logic that include first-order logic, computability, Godel's theorem, and other such things. These can be good books, but they rarely go beyond the definition of a Turing degree.

In either case, the undergrad books usually don't focus enough on computable functions and sets, because of their level. The number of undergrad books that include priority arguments is vanishingly small, but priority arguments are the cornerstone of recursion theory and its defining method of proof.

So if you see any modern undergraduate introduction to recursion theory that doesn't fall into the above categories, please let me know! Cooper's book cited in the article is about the only example I know of. CMummert 20:28, 29 September 2006 (UTC)

RE Kozen: Bummer, you and I just had an edit conflict. I actually saw Kozen 1997 when I was doing a survey of Turing -tuples. And then I re-found it when I was puckered about the Finite state machine article's definition of "state". I cc'd lecture #3 pp 14ff. His definition agrees with Minsky (woops that ole guy again) and with the engineering definition (sort of, kind of) and more importantly with the dictionary defintion L. status: stationary, standing. This is my viewpoint too. I can't imagine defining a finite state machine without defining "state".wvbaileyWvbailey

[edit] A tiny quibble: re Generalizations of Turing computability

"Recursion theory includes the study of generalized notions of computability such as hyperarithmetical reducibility and α-recursion theory, as described by Sacks [1990]. Strong analogies have been found between these generalized computability notions, which are of a set-theoretic character, and the classical notion of Turing computability, which is of an arithmetical character. Both Turing computability and hyperarithmetical reducibility are important in the field of effective descriptive set theory. The even stronger notion of degrees of constructibility is studied in set theory."

Melzak (1961) had this to say about the above in bold-face:

"It might be remarked that [Turing's] A-machines as well as most alternatives, are primarily oriented toward the logical task of symbol manipulation rather than toward the arithmetical task of calculating... it is our object to describe a primitive device, to be called a Q-machine, which arrives at effective computability via arithmetic rather than via logic. Its three operations are keeing tally, comparing non-negative integers, and transferring."

Simultaneously Shepherdson-Sturgis (1961/3) picked up the torch to find a model that would "carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested and started by Wang [1957]" (S-S p. 215)

Both Wang (1954/7) and Minsky (1961) placed Turing's A-machine in the camp of the symbol-manipulating logician but were trying to find an "basis for recursive function theory involving programs of only the simplest arithmetic operations" (Minsky 1961 p. 437) for the "applied mathematician and electrical engineers" (Wang 1954/7). Perhaps the word "Turing" should go away and the word "machine" be substituted, or "computability by machine" be used, etc. wvbaileyWvbailey 19:32, 26 October 2006 (UTC)

For my own use I have begun to use the word calculate for that which is done strictly by a person with paper and pencil or machine (i.e. mathematician writing a proof, or doing a calculation if by hand-- thus wouldn't recursion fall into that description?). But compute is reserved for the actions of a mechanism or by a person-as-mechanism (acting strictly as a mechanism: computer/computor) while in the process of "computing". Thus a person either using (i) a computer to do their accounts, or (ii) writing numbers and doing arithmetic by hand, or (iii) using a pocket "calculator", would calculating but the mechanism itself -- computer or "calculator" -- is computing. My dictionary agrees, sort of -- "calculate" comes from calx "chalk" implying "to write" , calculus "pebble" implying "to tally" and does not include "by use of a computer", but "to compute" (first usage 1616) is more ambiguous and allows "to calculate" as a synonym. I have observed at least in the olden days (e.g. Kleene, Minsky) a similar bifurcation of usage (but informally adhered to). Maybe in 2006 the usage has blurred the distinction? wvbaileyWvbailey 20:06, 26 October 2006 (UTC)

By arithmetical character I meant that Turing computability is closely linked to the structure of the natural numbers, to the point that the true theory of Peano arithmetic tells you everything there is to know about the computable and r.e. sets. The arithmetical character is that each completed computation can be represented as a finite object. In hyperarithmetical theory and α-recursion theory, it is no longer the case that each "generalized computation" can be represented by a finite object.

Since the previous paragraph is probably not easy for someone who doesn't already know recursion theory to understand, I'll try to clean up that section to make it more accessible.

I have never thought about keeping different meanings for calculate versus compute. Possibly this is because I accept the Church-Turing thesis that anything effectively calculable is Turing computable.

Please let me know any other thoughts you have about the article; I would like it to be as accessible as possible. CMummert 21:39, 26 October 2006 (UTC)

[edit] A scan of the article

The following words I flagged as could be linked (or not), as about 1/2 I would have had to look up to get the jist (more the X's the less I knew about the topic):

XRelative computability --> XXTuring reduction

XXReducibility,

XXdegree structure

Thue, XThue system, there is a link to semi-Thue system

Normal form

Decidable

Undecidable,

identity element

XXXXsimplicial complex

XXXhomeomorphic space

Diophantine equation

XXX "local strutural properties, global structural properties"

XXXalpha-recursion theory

Xfirst order formula =? first order arithmetic --> Peano axioms

In one place you used the abbreviation "r.e. Turing degrees" without defining what "r.e." stands for -- you do define it later in the article.

Some background/history might be useful (here or in another article with a recursion context):

The word recursion: First use (1616), comes from recur, to run again, L. re- + currere, (as in current). To repeat. Recursion: "RETURN". "the determination of a succession of operations on one or more preceeding elements according to a rule or formula involving a finite number of steps" (or not -- recursive: "...a procedure that can repeat itself indefinitely, or until a specified condition is met.")

Peano's definitions that followed the Peano axioms are recursive in nature and these came from Dedekind, correct? What possessed Dedekind and Peano to investigate this? Then what happened in the time between Peano-Dedekind, and "primitive recursive functions" (who first defined those?) and "recursive functions" of Gödel-Turing-Post-Herbrand-Church-Péter-Ackermann-Kleene etc? Wasn't it the antinomies/paradoxes of Russell ca 1900 and his crowd? and Cantor's method on top of it -- a kink in the Logicist/Finitist program of Hilbert? So was it Hilbert's problems that focused their work on "Foundations" and "Metamathematics"? Did Brouwer and his band of merry men play a role? This brings us up to ca 1950. We have Kleene's book (1952) (+ his professorship) which seems to me to be the magnus opus that set off Wang, Davis, Minsky, Melzak, Lambek, and ?? and all the host that was to split off to became the "theoretical computer scientists" (and some Russians too, isolated by the cold war). That left the die-hard recursion theorists. I loose the "recursion theorist" thread from 1960 on. Hilbert's tenth is solved. Gödel was on his last legs, Chaitin was a student. From 1960 point on -- who were the players? Who, or what "schools of thought", are the major players now? I know only the name Chaitin. You mentioned a few others... You do hint at "some of the big problems...".

Maybe you know of a good (historically-inclined) book -- "The history of recursion theory"?

On a more humorous take on the matter: the random wiki-student who bumps into "recursion theory" might ask: "When I grow up (choose a college, pick a field of study, declare my major, become more theoretical than computer science) I want to be a mathematician -- why would I want to be a recursion theorist?" I think the answer is: "Because you get to work on some really cool unsolved problems." The kid asks: "Yeah, such as? Explain..." My dad was an actuary. "What the hell is an 'actuary'?" I used to wonder. In 3rd grade I told people he sold insurance. Then when I got in high school he showed me his books of mortality tables: he definitely did not ignite in his son the fiery actuarial spark. How do you ignite the fire in the mathematics student? Hope some of this helps. wvbaileyWvbailey 03:19, 27 October 2006 (UTC)

Those comments are very helpful. I addressed some of them, and others I will have to think about for a while before I can find a way to write them. Some of the things you pointed out I wouldn't have noticed myself (I forget that the terminology is not familiar to the average person). CMummert 14:27, 27 October 2006 (UTC)

Glad to be of help. Another thought came afterwards as I was lying in bed -- would you consider Recursion theory to be one of (if not truly the only, or one of just a few of) the true "foundations" of mathematics? If so, or there's a tie-in to "foundations", this might ignite a few fiery sparks. Just a thought.

The fact that recursion theory deals only with the counting/couning numbers + 0 (positive integers) (is this correct?), that it is fundamentally arithmetic in that sense, is what attracts me to it now that I know more about it. (I thought this point was very good in the article intro). What also attracts me is that recursion theory (in the broadest sense -- algorithm-by-machine) is (I believe coming) very close to a problem around philosophy of mind, in particular where exactly are "the numbers"? For example (from the "foundations" talk page): Searle's (of Chinese Room fame) assertion that a machine is actually just a mindless, syntactic (symbol-manipulating) mechanism, that the meaning of the numbers (for some unexplained reason that I suspect has to do with enumeration i.e. "animal logic") resides only inside a human mind (and maybe the minds of crows!), hence here is where the numbers really are (etc. etc). (I am not sure what I believe, but anyway...) I don't recommend that this goes in the article, but it does suggest a powerful angle -- that recursion theory is working at the base of the edifice; Gödel-Turing-Post-Church et. al. made the edifice tilt a bit by mining away at its foundation. And more minings are underway (e.g. Chaitin) but simultaneously better foundation-reconstruction is in progress (examples?)... being a recursion theorist is very cool when you think about it that way. (I have to go and deal with the chipmunk that is raiding my bird-feeder...)wvbaileyWvbailey 16:10, 27 October 2006 (UTC)

Yes, Turing computability only deals with the nonnegative integers, and sets of them. Higher recursion theory uses other things, but is much less well known and is not as foundationally important. I usually identify finite binary sequences with natural numbers (both of them require understanding the word "finite" to define) and so I don't distinguish between manipulating finite strings of symbols versus manipulating natural numbers.

I would say that recursion theory is "foundational" mostly in its definition of Turing computability as the correct formalization of effective calculuation. This definition is almost universally regarded to be the right one. It is required for proofs that certain problems are not solvable by computer programs. It also makes possible the definition of random reals numbers originally given by Martin-Lof. I don't want to speculate too much on foundations in this article because I'm not trained in history or philosphy and because my random speculations would probably be original research from the WP point of view; I have already pushed it as far as I think I can. CMummert 16:27, 27 October 2006 (UTC)

RE Turing computability, Gandy and Soare: after reading these I am now wondering about the question of computer/computor versus computation with a "machine-in-the-broadest-sense". Can a "machine-in-the-broadest-sense" calculate more than a Turing-machine-computer/computor? There is still this niggling little thing bothering me about "analog computation": suppose all the computations in the "analog box" were analog in nature(but not necessarily linear, e.g. the squashing/sigmoid function is my favorite), converted only at the "end" to discrete "numbers"? (If it were just up to me I would break Post-Turing Thesis into three, in the manner of Kleene (1952), pull in Gandy-Soare etc.)

I hear you about the original research problem; I'm confronting the same issue in an article as we speak: "Is it, or is it not, original research?" I see you have been busy -- the article Algorithmically random sequence -- I don't know much about them but find random number generation fascinating. (RE chipmunks: I put a bunch of seeds out for the chipmunk so it leaves the feeder alone. It is busily filling its cheeks with seeds and scurrying back to its little burrow under our front porch. It will be hibernating soon. I'm sure you were just dying to hear the follow-up to the chipmunk problem.) wvbaileyWvbailey 18:56, 27 October 2006 (UTC)