User talk:CBM/Archive 2

"Function" article, Pooryorick 22:13, 23 August 2006 (UTC)

Thank you for the tips. I do think that wordiness is often an impediment to understanding, and so are context switches, which is why I was trying to get the sentences about "less than" to be contiguous. As I study math formally (although independently) for the first time, I believe I can contribute much feedback about where the math articles on Wikipedia lose the lay reader. Although it is obvious in retrospect, I spent a good 30 minutes trying to understand that first definition before writing a comment about it. I'd like to help make these pages more accessible to people like me.

Decision problem.

Hello. You've just reverted my changes on Decision problem/Equivalence with function problems. As I can understand your POV about the definition of function problem, still, there were some other changes I made. Could you look under the Talk:Decision problem where I tried outline my doubts and propositions? Thanks. --SalvNaut 00:38, 10 September 2006 (UTC)

I put a comment on the talk page there explaining the revert. I also made several changes to address your comments about computational complexity. CMummert 00:41, 10 September 2006 (UTC)

Automated gramtical changes

I'm sorry to hear there are flaws in my make-shift editing script, I can solve most of the problems you noticed by refraining from clicking "correct capitalisation" thanks for pointing this out. -- JiMoThY^TALK 14:50, 17 September 2006 (UTC)

Thanks for the response re "recursion"

Hi, wvbailey here: I won't do anything to the computability or recursion articles other than (if appropriate, eventually) make some links to Random Access Machine, which I'm working on now, and to Register machine. I've got a copy of your reference Soare (1995) -- will read it carefully. Interesting in Soare about the Peano Axioms, in particular induction-- I had noticed that there is a variant of the register-machine model that uses essentially the Peano axioms to compute its numbers. What is interesting is this u-operator business, the wiki article of which I read but don't understand. (The article needs an example). I also re-read Minsky (1967) and I kind of see a faint glimmer ... very faint.

At this point I am very perplexed about why "recursion" isn't considered "just" another name for mechanical computation (everything is mechanical at some level) i.e. done by "a computor/computer" distinguishing and writing or erasing and symbols on a sheet of paper and proceding "step-wise" per a set of rules. Maybe that's the point ... But wouldn't this relegate "recursion theory" to oblivion? And "recursion" to a synonym for induction? Hopefully Soare will clear this up. wvbaileyWvbailey 16:13, 18 September 2006 (UTC)

Primitive recursive

Okay, I've left a note on the article's talk page. Not sure I'll have time to help fixing it right now though. Cheers. Pascal.Tesson 19:32, 18 September 2006 (UTC)

Added something to the mu-operator page

I added Kleene and Minsky references with a lot of secondary info as I came across it and worked through it. But the "recursion" articles still have a problem with all these defintions of recursive functions. The older texts are using "general recursive" where I think you are using "mu-recursive". For a newbie this is damned confusing stuff. Somewhere it would be valuable to have a table or list or something that defines the terms, even if they are obsolete, because they are deeply embedded in the (historical) literature. I've been able to gleen (probably incorrectly) something like this:

• mu-recursive = total/general recursive = primitive-recursive + mu-operator ??
• total recursive (obsolete name) ??
• general recursive (obsolete name, but equivalent to total recursive) ??
• primitive recursive
• partial recursive-- partially defined mu-recursive ??
• others?

If this is true then there seems to be a kind of heirarcy:

1. primitive recursive
2. partial (mu-)recursive
3. "full" mu-recursive

Have I got this right? Thanks, wvbaileyWvbailey 16:50, 22 September 2006 (UTC)

Here is what you are looking for:

1. primitive recursive function
2. general recursive function - a function defined in terms of a finite set of recursion equations, a la Kleene and Godel. No longer widely used as a foundation for computability.
3. mu recursive function - a function defined in terms of primitive recursive functions and the mu operator.
4. recursive function - synonym for computable function, with no connotation for how the function is defined except that it is computable.
5. partial recursive function - synonym for recursive function, emphasizes the function may not be defined for all arguments
6. total recursive function - a recursive function that happens to be total.

The classes of recursive functions, mu recursive functions, and general recursive functions are the same.

CMummert 16:58, 22 September 2006 (UTC)

I decided recently that many of these terms were unclear. So I am restricting myself to just "primitive recursive", "total recursive", and "partial recursive" and forsaking all other terminology (such as "recursive" or "computable") as ambiguous. Every primitive recursive function is total recursive; and every total recursive function is partial recursive. But the reverse inclusions do not hold. While the definitions of primitive recursive and partial recursive usually do not cause any confusion, it may in some cases be impossible to tell whether a partial recursive function is total recursive. JRSpriggs 03:56, 24 September 2006 (UTC)

The classical terminology is certainly unclear. That was one of the arguments Soare made in favor of using computable instead of recursive, since recursive carries so much baggage. But partial recursive is a standard term, and is still used by computer scientists. I wouldn't want to go through all the articles and force them into one terminology scheme. CMummert 12:53, 24 September 2006 (UTC)

I've read and reread Minsky (1967) a bunch of times and this is what he says (my guess is he follows Kleene (1952) in this). Granted, he may be outdated. But so many of these words are to be found in "the literature"...:

1) "primitive recursion" is a process of creating numbers by starting with a "base step" and then applying "induction" over and over

2) a "primitive recursive function" is one defined by the following processes: 0(x), Successor(x), Composition, and "primitive recursion".

[Best as I can determine: Unless one resorts to the additional histrionics of godelizing and fancy encoding, the register machine models represent the primitive recursive functions. The addition of "indexing/indirection" to the register machine model renders it (easily shown to be) general recursive (Melzak 1961). With the addition of indexing/indirection the register machine model graduates to the status of "random access model (RAM)" (instructions separate from the registers aka Harvard architecture). With the placement of "the program" in the registers togehtere with their parameters/data, the RAM graduates to the status of "Random Access Stored Program" model (RASP) (i.e. the "Universal machine" version of the RAM with von Neumann architecture). All of these, including the register-machine models are considered Turing equivalent, but I personally have concerns about the demonstration for the register-machine model because of what is required of its finite-state machine]

3) a "general recursive function" is defined by the four operations of 2) plus use of the mu-operator. "...functions computable by Turing machines are general recursive. We will prove the converse in the following chapters (p. 184)"

"If a function can be defined by the apparatus of primitive recursion, together with use of the minimzation operator mu, then it is a general recursive function (or more briefly a recursive function)" (p. 186)

By this definition, "mu-recursive functions" seems synonomous with "general recursive functions". Apparently they are not. Why?

4) a "recursive function" is a synonym for (3)

5) "partial recursive function" is synonomous with "partial function" and is 3), 4)defined for some but not defined for others of its variables

6) "total recursive function" is synonomous with "total function" and is 3), 4) and defined for all values of x. But:

"In the literature 'total-recursive' is a synonym of 'general recursive' "(p. 186)

Soare used "general recursive" as synonomous with "recursive" (Definition 1.2). Where I'm having troubles is when I looked at the wiki articles on recursion I found (a) the use of "mu-recursive" and not "general recursive", and (b) no table of generally-defined terms.

I would caution folks that the unspecified (vauge) notion of "computable" seems to come in two forms depending on whether or not availability/application of the mu-operator or its equivalents is "easy" or not, i) primitive-recursive computable and ii) general-recursive computable.

Noteworthy that Sipser (2006): "Introduction to the Theory of Computation, Second Edition", has nothing to say about "recursive functions"-- what little he does say comes under the guise of "the recursion theorem". wvbaileyWvbailey 15:55, 24 September 2006 (UTC)

It sounds like Minsky is contradicting himself. By using "general recursive" to mean either total recursive or partial recursive as it suits him. Also partial functions are a MUCH larger class than partial recursive functions. And total functions are a MUCH larger class than total recursive functions. We cannot make sense out of what does not make sense. So give up the idea of creating a glossary or dictionary article to clear things up. It cannot be done. JRSpriggs 03:06, 25 September 2006 (UTC)

The idea of a general recursive function, as set out by Kleene and Godel, is that it is defined in terms of a set of recursion equations. For example:

f(0,0) = 0

f(n,m+1) = f(f(n,m),m)

f(n+1,m) = f(n,m) + 1

Not every set of recursion equations defines a function, and in some cases there is not a unique function, so there are a lot of techinical issues to deal with. Since a function defined by recursion equations can be computed using the μ operator, and the μ operator doesn't have these technical issues, defining the class of computable functions in terms of the μ operator became standard, even though the name general recursive was still used. But modern texts no longer use the phrase general recursive, and just say recursive or computable instead.

Remember that the field is under a hundred years old, and in the 1960s was only 30 years old, so terminology was still in flux. Sipser's book uses computer science terminology, so it says decidable instead of recursive. Kleene's recursion theorem is named for a different type of recursion than the name general recursive implies. CMummert 11:35, 25 September 2006 (UTC)

Yikes. You folks are the experts; I'm just a confused wiki-reader. Shouldn't some of this go into an article? Old-guys like myself, over the years, have encountered a plethora of words (e.g. in The Undecidable, Kleene 1952, Minsky 1967) and wonder what is going on when we encounter, e.g. "mu-recursive" and can't find "general recursive". I'd certainly wouldn't complain if "general recursive" was put on the shelf in favor of "mu-recursive" (or just "recursive"), but would find interesting an explanation of where/why the name "general recursive" is disappearing.

As for Minsky (1967) ... hmm ... he is not without his faults. E.g. he used a peculiar, unconventional representation of state diagrams (for Turing machines) when the engineering literature had been available for a good 15 years. I tried to "run/simulate" one of the diagrams for a "multiply algorithm" without success. wvbaileyWvbailey 14:18, 25 September 2006 (UTC)

There is a series of emails beginning with http://cs.nyu.edu/pipermail/fom/2006-September/010796.html that may be of interest. CMummert 23:22, 25 September 2006 (UTC)

Another question; the Soare (1995) paper

What ARE they talking about? He quotes Gandy (1988) as saying that "Turing's analysis makes no reference whatsoever to calculating machines. Turing machines appear as a result, a codefication, of his analysis of calculations by humans." (p. 11)

au contrare: After his two proofs (circle proof and print a 0 proof), On page 137 (Undecidable, near the bottom), after Turing has spent 3 pages defining how computation is done by a computor, he says:

"We may now construct a machine to do the work of this comput[o]r. To each state of mind of the comput[o]r corresponds an "m-configuration" ...etc.... The machines just decribed do not differ very essentially from computing machines as defined in §2, and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the comput[o]r." (p. 138)

I suppose Gandy could make a (very poor) argument that a "calculating machine" and a "computing machine" are different, and that there are two "theses" but how so? Turing draws an utter equivalence in the outcome between "the two processes": human and machine. H <--> M. [They are indistinguishable]. Do you know any of these guys -- Gandy, Soare? I suppose I could google them. I'll do that. As I am reading this now (always subject to change... ) the recasting of Turing's Thesis into (TT-Computor) sure seems bogus.wvbailey`Wvbailey

I believe Gandy (and Soare, by reference) is saying that Turing's analysis of which functions are effectively calculable is based on his analysis of what a human could calculate, and this anlysis is used only in retrospect to motivate the definition of a Turing machine. This is, undoubtedly, a correct summary of Turing's paper. I believe Soare includes this quote because he wants to distinguish between what he calls Turing's thesis and what he calls Church's thesis, which are both different from what he calls the Church-Turing thesis (see p. 15). One of the issues Soare wanted to bring up was his opinion that what is generally called Church's thesis should be called the Church-Turing thesis instead, and should be viewed as a definition of computability rather than a thesis about it. CMummert 20:31, 22 September 2006 (UTC)

Despite initial misgivings I found Soare very interesting. And after reading what you wrote I agree that the Soare-Gandy point is well taken: that indeed Turing modelled his a-machine after a man's computational processes, so we can expect that his a-machine will compute the same "class of functions" as the man. So we wonder: what about the converse: Suppose the machine is not so restricted to compute "like a man", can it compute "more functions?"

So Gandy (1980) tries to demonstrate that indeed any "discrete, deterministic mechanical device that satisifes principles I-IV" computes the same class of functions as an a-machine, and as a human computer. (Or not .... Gandy sure has a hard time stating his concepts and conclusions clearly. And he starts out so good.) As an engineer I have major issues with Gandy's thesis and his use of 'state' -- he assumes it as a given without extensive, thoughtful definition, unlike Minsky (1967) and other authors who are very cautious here. Bad move on Gandy's part. (This is a sore point -- I ran into the same issue when I butted heads with the gatekeepers at the finite state machine article. I finally gave up in disgust.).

But anyway, thanks for putting me on to Soare. Through him I came to read Gandy -- I'd encountered the name in Gurivich but after seeing the name in Soare it became time to read Gandy for myself. wvbaileyWvbailey 17:10, 24 September 2006 (UTC)

Halting problem attribution to Davis

This is a history of how this came to happen:

(1) I had been fussed about my observation that Turing did not coin "halting problem" -- his 1st proof had to do with a machine that could detect "circles". So I probed the lietrature backwards in time until I came to a dead end at Martin Davis (per the current article's analysis). After a long dialog Lambian proposed that I write to Davis, and I did. here is Lamian's message to me:

You might try asking him directly, he's a nice guy. Here is his NYU web page, with e-mail contact, telephone, everything: http://www.cs.nyu.edu/cs/faculty/davism/. --LambiamTalk 00:41, 4 June 2006 (UTC)

I wrote Davis twice, and reported this to Lambian:

Quoting from an e-mail is problematic; it is "unverifiable" under Wikipedia's definition. But if you can know of a published source (book or article) in which Davis first used the term, you have my blessing (if it counts for something) to cite that while using a phrase like: "The term Halting Problem was coined by Martin Davis <citation>." --LambiamTalk 13:33, 4 June 2006 (UTC)

Davis did indeed use the word "halting problem" in his text. And in his e-mails he said he coined the phrase. But he graciously attributes his proof to a "proposed proof" byKleene (1952) -- he gave me the exact place to look, its just a sentence. And in the second e-mail he points out that the Turing degree of Turing's second proof (the business about printing a 0) is the same order as "the Halting problem", thus as far as he was concerned Turing's print-a-0 proof is in fact "a Halting proof" without the name attached (because Turing's a-machine doesn't halt!). And the Turing degree of the first proof is "harder".

From this (I have my 'lawyer' hat on now) the following facts/findings emerged: (a) nowhere does the phrase "halting problem" appear in any of Turing's work, (b) that Turing's second proof is Turing-degree equivalent to "the halting problem", but not the first, (c) that Kleene (1952) suggests in passing the proof in its current form, (d) that Davis says he coined the phrase in his book (ca late 1950's), (e) the earliest use I have been able to find is in fact in Davis's book in the form of his (Davis's) proof.

From this (I have my 'judge & jury" hat on now) I conclude that to attribute the phrase "the halting problem" to Turing is to perpetuate a blatant falsehood. However, we can attribute an equivalent form of it (he used his proof #1 to prove #2) whereas the Davis-Kleene proof is different) to Turing.

(2) I never finished the task of writing this up. My thought was to erase most of the stuff about the sub-authors and just deal with the real stuff (a)-(e). But to tell you the truth I didn't know how to proceed. I (hanged?) hung up on the exact problem you raise, and frankly got bored with it (I satisfied my curiousity).

The way I look at it now is this: I was new to wiki at the time (Jan '06), and what I started out to do was a survey because of my curiosity re my finding (a) and frustration at icky article with zero references. But I arrived at a wikipedia-based blind end: I have no 3rd-party-peer-reviewed source that says that Martin Davis coined the phrase. Worse, I cannot even say that he says he did, because that too is hearsay by wiki-standards (i.e. two e-mails to me).

As you say it's a fine line we tread. I see any wiki-contribution other than a simple steal as synthesizing through a mind and thus a POV -- there are just degrees of it. I'm very open to cutting. Suggestions how to proceed? Perhaps you might want to move a cc to the Talk Page and take a whack at it? Or here, or at my talk page. Or whatever... wvbaileyWvbailey 15:36, 27 September 2006 (UTC)

I re-read the article and your diagnosis. The article is too long and very unfocused. I agree that the history section needs a severe pruning. If so, then many of the references (e.g Principia Mathematica) could go away (I believe I added all but a few, maybe all, I don't care... use your judgement). I will leave this pruning to other minds. I really like the 3rd footnote -- Kleene's usage is the first known expression of the halting problem, just as Davis reported. Davis then provided a proof and called it the halting problem in the proof. Now whether this synthesis is a POV or an expression of facts-as-findings I dunno.

Then there is this whole issue of in-line references ... this article fails miserably. If you haven't already, see the Hilbert talk-page: They are being beaten about because they have few or no in-line references. One editor griped about my use of so many on the Turing machine page but I remain steadfastly unremorseful re the good article policy. wvbaileyWvbailey 16:00, 27 September 2006 (UTC)

I suggest that you simply state what you do verifiably know, i.e. that Davis used the term in his proof in such and such a paper on such and such a date, and remove all unverifiable references to anyone else supposedly having coined it. It is not necessary to say that Davis was first. Just do not say that anyone else was. JRSpriggs 06:05, 28 September 2006 (UTC)

Thought

I have posted this to ScienceApologist's page, but I thought I would post ithere as well, since I was much impressed with your contributions over the recent citation debate. The recent controversy that we have been engaged in over inline citations has exposed, I think, a serious flaw in the way in which Good Article status is conferred. The possibility has been floated of forking distinct areas into a separate wiki in order to circumvent the naïve dilettantism that seems currently to pervade the GA process. I wonder, however, if much the same can be achieved through a rethinking of the good article process itself. There are many areas – physics, math, music, literature, pokemon, history, etc… - that have portals and named participants. Instead of having a group of 20 or so uninformed generalists undertaking the daunting task of rating articles as good or not, it would be preferable to divert the review process through editors involved in those distinct portals, a sort of fusing good article status with peer review. As a result of this debate, I have looked at a number of good article reviews and I find that the mostly the suggestions are of a “please cite your sources nature” rather than a committed engagement with the material. In effect, I wonder if it might not be worthwhile to investigate the possibility of having the concept of Good Articles divided up by category with respect to review for inclusion or not: thus Good Articles in Physics, Good Articles in Music, Good Articles in Pokemon (shudder) etc…. While this debate has centred around scientific articles (not my area of expertise) I can easily see much the same being applied to music, literature, etc… where citations are being demanded for basic facts that nonetheless may be unknown to an uninformed reader. A proposal could be floated and the various portal pages invited to intervene with commentary and ideas. Eusebeus 22:55, 28 September 2006 (UTC)

If it isn't possible to reach consensus with the GA regulars, it may be possible to find consensus within the math project. The physicists have a suggestion about it on their project talk page. But intraproject GA systems would not be ideal, I think, because of the conflict of interest in setting up standards for yourself to meet. Also, as I have pointed out elsewhere, it is bad for my project if newly pedantic standards for GA turn into pedantic standards for FA. I came to wikipedia for reasons such as these [1], [2]. I would like to convince the GA regulars to adopt scientific standards rather than aim wikipedia at an 8th grade level, so that readers who come from search pages will not be surprised by what they find. CMummert 00:18, 29 September 2006 (UTC)

CMummert 00:18, 29 September 2006 (UTC)

When my nephew (8th grade) told me he was working on fractals in algebra, I went to his computer and together we explored the Fractal page. (I discovered, once again, no references. So I added what I had acquired years ago when my own kid was taking 8th-grade math (e.g. the Macintosh generators on a disk, and another book in my collection).) So there I was with my nephew staring at the computer screen. I didn't give one teensy-weensy f*ck about scientific standard-quality, post-college-graduate-level content. I only cared about raising my nephew's 8th grade understanding, about getting him enthused by showing him some nice fractals (it worked; he was entranced).

A much deeper issue swims beneath the surface: "Mission" - the purpose of wikipedia. Who does it serve? I have no idea; Wikipedia is clueless. I've seen articles go from the fractal article (a bit more advanced than 8th grade, but not much), to the busy beaver article where the readers begged for less strenuous presentation (actually: any presentation)...(I've poked around at it but haven't tackled for fear of having my fingers stomped), to a number of foundations articles that .. oh my god... who was this ... quote <content> unquote ... written for? Again and again I ask: why would a PhD-level person be searching wikipedia for content in their subject area? What (I opine) an article should do is guide the curious-but-naive/novice/newbie reader from the elementary toward the complex and at last end with citations/references for more information. (E.g. I liked your two levels of references (undergrad and advanced). That was a nice innovation I haven't seen anywhere else). Links can provide the jumps to higher and higher (deeper and deeper) levels of 'content' (or, I hypothesize, lower and lower, more naive levels too)-- so both novice and advanced articles are necessary. This is a tough task. In the best scenario, years will pass before wikipedia gets to this quality level. wvbaileyWvbailey 01:23, 29 September 2006 (UTC)

I agree that it will be years before WP is up to speed. I agree articles shouldn't be written for PhDs, and they should be stratified in how much background they assume. Some should be for a 10th grader, some for an undergrad, some for a math major undergrad. None should require graduate school to understand.

I thought the sorted references were nice because they let the reader know which book to pick up first without recommending a particular book. And they warn readers that particular references may be difficult to read.

By the way Busy beaver does need editing, and I would back up any changes that improve the article. Don't be afraid to stand up for yourself and make changes. CMummert 01:49, 29 September 2006 (UTC)

Thanks for the input on the cite issue. You might be interested in Wikipedia:WikiProject Mathematics/Wikipedia 1.0, which is where general mathematics article assesment is taking place. Currently I'm about the only mathematician doing much work on grading maths articles and it would be great to get some more input. The way things work is that any editor can grade an article by placing the Template:maths rating tag on the articles talk page. In addition to the standard assesment FA/A/GA/B/Start/Stub I've added a B+ rating, which is for the better mathematics articles which don't quite meet GA standard. The full list of articles already graded on the talk pages is at Wikipedia:Version 1.0 Editorial Team/Mathematics articles by quality. --Salix alba (talk) 09:31, 29 September 2006 (UTC)

Report me to appropriate authorities then

Bravada, talk - 00:31, 3 October 2006 (UTC)

Maths / Wikipedia 1.0

First up, thanks for your contributions in grading and adding articles, especially as they're in a area where my mathematical knowledge is definately lacking. Could I just be so bold as to request that you include the comments you make on WP1.0 page be inlcluded as suggestions on the article's talk page via the "comment" option of the maths rating template? That way it's easier to target effort for improving the article.

Many thanks. Tompw 21:57, 6 October 2006 (UTC)

Certiainly. I didn't know about that option, but I'll use it in the future. CMummert 22:09, 6 October 2006 (UTC)

Interesting intermediate-level text treating recursion etc

I remember that you asked me to let you know if I found any texts that treat recursion in a manner more suitable for non-recursion theorists -- I happened onto Burgess's rewrite of Boolos and Jeffrey -- Boolos, Burgess and Jeffrey (2002), Computability and Logic Fourth Edition, Cambridge U. Press, Cambridge England. Have you encountered it? It starts off with the intention:

"...for students of philosophy, mathematics and other fields who desired a more advanced knowledge of logic than is supplied by an intoductory course or textbook..."

The book is divided into three major sections: "Computability Theory" (8 chapters), "Basic Metalogic" (10 chapters), and "Further Topics" (9 chapters -- what caused me to buy the book was the chapter 22 on "Second-Order Logic", that and the chapters on "abacus-machine computability").

In fact I found it in the philosophy section of the UC Riverside bookstore! It has some really interesting chapters on stuff I'd heard of but know nothing about such as Presburger arithmetic, Robinson arithmetic, Ramsey's theorem, etc.

With regards to recursion they treat it coming first from "Turing machine computability" then "abacus (Lambek) machine computability" (first time I'd ever seen anyone use the "Lambek model" I changed the register machine page after reading this). They then show how to simulate the primitive recursion "operations/operators" with abacus machines, and included the minimization operator leading to (I still don't understand this stuff...) chapter 6 on primitive recursion where the minimization operator appears again, then chapter 7 on 'recursive sets and relations', chapter 8 on "Equivalent Definitions of Computability". They do not use tfouhe word "mu-recursive/recursion", just "recursion".

Your take on this book would be interesting. wvbaileyWvbailey 20:30, 10 October 2006 (UTC)

I haven't seen the fourth edition, but the original Boolos and Jeffry book was very good (I just now looked at the TOC for the 4th edition on amazon.com). An undergraduate logic course could not be criticized if it covered a significant portion of this book. The previous editions were very terse, and if this edition is the same then it will be slow going for individual study.

The phrase "μ-recursive function" is only used in the context of comparing various equivalent characterizations of the computable functions. The term "minimization operator" for the μ operator is common.

I disagree that the book is a "recursion theory" book, though. It doesn't spend much time on Turing degrees, priority arguments, etc. because it is just covering the basic concepts of computability. Similarly, an introductory book in number theory might investigate basic properties of Abelian groups but wouldn't be a "group theory book".

I'll have to find a copy of the book to read their take on second-order logic.

CMummert 20:52, 10 October 2006 (UTC)

You are correct...re a "recursion theory book" there isn't much recursion beyond where Minsky went, just a better treatment (quite similar actually). No 'Turing degree' in the index, no 'priority arguments'. I'll keep looking. Probably we're searching for the book you need to write! wvbaileyWvbailey 00:17, 11 October 2006 (UTC)

Change to Mu operator

User talk:Duja just added (merged in) some stuff which I do not understand. Can you make any sense out of "The μ calculus is a model of calculi that can be used for model checking of temporal logic properties. The LTL, CTL and CTL* logic can be translated into the modal μ calculus for verification."? JRSpriggs 09:40, 24 October 2006 (UTC)

I can barely make sense out of it, but I think it might have been an administrative response to a request on Wikipedia:Requested moves. I moved the cryptic part to the bottom in the external links section, and I'll unmerge it soon unless someone can explain why it belongs in that article. CMummert 16:38, 24 October 2006 (UTC)

I am also not very happy with the merge: the mu operator has become a bit more messy, since the description of the mu calculus can now be found in the references section. The whole thing started when I proposed to rename Modal μ calculus to Modal mu calculus. After that, there was a little debate on the name of the article, until User talk:Duja merged the page with the mu operator. Seeing the merged page and the above response, this wasn't the best thing to do. eboy 18:17, 24 October 2006 (UTC)

Primitive recursive functions

Hi, wvbailey here (as I remember: the evil-doer who added the stuff in the references). I have been adding stuff to the algorithm characterizations page (BTW please if you can find time review the Kleene characterization for accuracy/content, given that someone hasn't destroyed it already). It pulls in Kleene (1952) and his various definitions. The minimization operator appears on cue. After reading both the relevant Minsky (1967) and Boolos-Burgess-Jeffrey (2002) (with their very similar derivation of the 6 recursive-function operators from their counter machine models), then pawing about the Ackermann function and Rózsa Péter's diagonalization-demo that Kleene mentions, I found in Kleene (1936? 35?), in a footnote, his describing the need for a minimization operator.

But I still don't get it. I get the primitive recursive functions, now (more or less) but not the mu-operator. The wiki article is no help at all. About as close I can get is that: something really nasty happens when really big numbers get made with primitive recursive functions (do they diverge, never terminate?). But what, and why? And Rózsa Péter's diagonalization -- what does that have to do with Ackermann's super-exponentiation? Is the u-operator just a trick to terminate a monster-calculation before its naural time (i.e. before the ends of the universe)?

I also noticed that the split of Church-Turing Thesis into Church thesis Church Thesis Church's thesis Church's Thesis and Turing's Thesis, Turing thesis Turing Thesis Turing's thesis. Turing's thesis is very prominent in Kleene (1952) (and Soare, etc). But wiki has no article on it. Hmm. wvbailey

I fixed Turing's Thesis and Turing Thesis. Apparently the search window on the "front page" is insensitive to capitalization but the links are capitalization-sensitive. That I don't know how to go about fixing. wvbailey

Thanks for pointing out those red links; most of them should be redirected to Church-Turing thesis. Whether there is a diference between Church's thesis, Turing's thesis, and the Church-Turing thesis depends on who you ask. Soare's article argues they are different. But I think a single wiki article is enough; we can describe the relative differences in a single article.

I don't mind references; in fact, I wish that more articles had more references. I think my position was that historical info ought to go in the main article. The annotated references at Mu operator are still there.

The motivation for the mu operator is this. Suppose that you have the ability to effectively determine whether a natural number is in a particular set A. And suppose furthermore that you have an effective function f such that you can prove that if you start with any number n and successively compute f(n), f(f(n)), f(f(f(n))), and so on, eventually you will find a number in A. Define a function g that takes input n and returns the first number in A that can be found by iteratively applying f. Then g should be effective as well. This follows from the Church-Turing thesis: since I told you a mechanical procedure for finding g(n), the function g should be Turing computable. And, if if you read "effective" to mean "computable" then this is correct - g will be a computable function if A is decidable and f is a computable function. But even if f is a primitive recursive function and A is a primitive recursively decidable set, g may not be primitive recursive. The problem is that although you know that for each n you will eventually find g(n), you don't know how many iterations are required. So the function h(n,t) which applies f to n iteratively for t iterations will be primitive recursive if f is. The definition of h is

h(n,0) = n

h(n,t+1) = f(h(n,t))

But the function g is definable as $h(n,\mu t\,[h(n,t)\in A])$ but not generally definable as a primitive recursive fuction (without the mu operator). So if you are interested in having a syntactic definition for every computable function, you need the mu operator as well as the syntax used to define primitive recursive functions. It's essentially just a programming language in which the mu operator is used to construct loops.

CMummert 21:29, 24 October 2006 (UTC)

I've read the above, haven't been able to digest yet, but that's me, not your explanation. I opened up ole Minsky and re-read pertainent parts. He does not include the identity operator in his list of primitive recursive functions. Any guess why that would be? Everyone else seems to use Kleene (1952) "Basis B" with φ=0 (Kleene p. 223 vs p. 219). Here's old Minsky again:

Definition:

Any function that can be defined in terms of 0(x), S(x), composition and primitive recursion is called a primitive-recursive function. (p. 175)"

(Just a parenthetic ... puzzlement: There is cryptic stuff in Minsky (p. 214) that seems to say that a Counter machine cannot really "simulate" a general-recursive function. But he doesn't come right out and say so. And according to some of his little notes -- If you can build a "universal machine" with a machine model, then you've proven that the machine is equivalent to the general recursive functions (or something to that effect). So given Minsky's "cryptic comment" the primitive counter machine should not be able to be turned into a "universal machine." But in his famous proof (1961) he claims you can make it so with a single register. So there is something I am not getting, bigtime. It has to do with indirect addressing on a bounded versus unbounded register, and the u-operator, I'm almost certain.] wvbaileyWvbailey 23:21, 25 October 2006 (UTC)

Unfortunately, I don't have Minsky's book, so I can't look it up. CMummert 00:27, 26 October 2006 (UTC)

Thanks, not to worry, I will keep poking until I get to the bottom of it. Minsky says that the IF-THEN-ELSE construct of "the McCarthy Formalism" ... ahh I just found something... the IF-THEN-ELSE replaces both the primitive recursive operator and the minimization operator. So he claims that if we have available the Zero, Successor, "Equality of Numbers" <== (hmm... this just sneaked in!!), Composition, and the IF-THEN-ELSE we have general-recursive equivalence. I will have to research the "McCarthy Formalism". No need to respond, just a followup. wvbaileyWvbailey 01:30, 26 October 2006 (UTC)

The capitalization of the first letter of a link does not matter. The software folds it up. But other letters in the link must be either capital or diminuative as in the title of the article. Also watch out for the difference between hyphens "-" and ndash "–" and mdash "—". JRSpriggs 07:51, 26 October 2006 (UTC)

Did I make a link somewhere that didn't work? I usually verify that the links I create are blue and go to the article I want. CMummert 10:42, 26 October 2006 (UTC)

Maybe this is in response to my trying to fix the Turing's thesis Turing's Thesis links. wvbaileyWvbailey 13:59, 26 October 2006 (UTC)

I am sorry that I was not clear. I was responding to Wvbailey's message which said "I fixed Turing's Thesis and Turing Thesis. Apparently the search window on the "front page" is insensitive to capitalization but the links are capitalization-sensitive.". When I first tried the links, I was stopped at a redirect because of multilevel redirection. So I fixed the links. The error had to do with his using hyphens instead of ndashs in the redirects he created. JRSpriggs 06:15, 27 October 2006 (UTC)

L'hop's Rule

Thanks for your input on my proofs: specifically, that they are wrong. I'm serious. I'm pretty sure about the first one, but not the second one. Are they generally correct, but not mathematically thorough? May I ask what is wrong with them?

(Note: the second is probably wrong because, by the same logic,

$\lim _{x\rightarrow 0}\sin 2x=\lim _{x\rightarrow 0}x$

insert fallacious step here

$\lim _{x\rightarrow 0}{\frac {\sin 2x}{x}}=1$

which is untrue.)

As for the local linear proof, which I'm positive is solid (if I didn't overlook any stopgaps), do you know somewhere where it might be already published so that I can use that as a source? Thanks.

-Gracenotes ^T § 20:15, 30 October 2006 (UTC)

The comment about having them published was by someone who didn't take advanced math. The proofs you presented, when recast in a more mathematically correct form, are not new. You are doing well if you are 16 and able to work with such things. The next place to look would be an undergraduate level real analysis book, where you would be able to learn the details of how to prove things about calculus.

I didn't read your proofs in detail, but I thought the first one said something like "let e be infinitely small" which doesn't really make sense - only 0 is infinitely small. I don't have any more time this evening to comment on the proofs, unfortunately. CMummert 21:07, 30 October 2006 (UTC)

Thanks. I didn't create the proof by the mean value theorem -- that proof was already there. The local linearity proof was my contribution. Thanks for your comments. -Gracenotes ^T § 22:05, 30 October 2006 (UTC)

Verification system

Hi there; thanks for your reply on the village pump. With regards to the articles you gave, the parsing doesnt work too well with them because i haven't got support for some of the reference styles yet. At the moment, the bot simply checks for the volume of the references in-line with the paragraphs, so it can give a rough estimate as to which parts of the article are likely to be referenced, and which aren't.

I'd love to be able to expand the program to be more intuitive, but at the moment, it's a part-time occupation aside from my research. If you could give any more comments, reccomendations or help, i'd be glad of them :-) JCraw 15:46, 9 November 2006 (UTC)

Making an automated scan seems like a very difficult task to me. I don't see how to make the parser that smart (it would essentially have to read natural language), so it will only be able to find references using certain wiki tags that are not universally adopted. It might be usful for articles where those tags are expected. An easier problem might be to just list those articles that have no section named References. This would locate the worst of the worst, and I would be very interested in a list of these articles. CMummert 01:34, 10 November 2006 (UTC)

Closure conditions in Henkin semantics

I notice you removed all my mentions of closure conditions in Henkin semantics from the article on second-order logic. However, I think you should reconsider. In Henkin's "Completeness in the Theory of Types", which you cite, he does indeed have a notion of an arbitrary frame, but also introduces the more restrictive notion of a general model, which is subject to precisely the sort of closure conditions which would arise from comprehension axioms. And then, importantly, he proves his extension of Godel's completeness theorem for these general models, rather than for arbitrary frames. The sense in which I have always heard the phrase "Henkin semantics" used is that which refers to these general models, rather than to arbitrary frames, and a quick Google search seems to back up this intuition as to how the term is generally understood.

Clearly, you are quite knowledgeable in this area, so I'm sure you can set me straight, but I really do believe that nine times out of ten, "Henkin semantics" is used to refer to the semantics arising from the general models of Henkin 1950, rather than those arising from a looser concept, and that the article should reflect that. At the very least, that Henkin managed to prove soundness and completeness of an effective proof system with respect to such semantics should be noted. -Chinju 10:20, 30 November 2006 (UTC)

I think that what you are saying is that many people (I checked the references for Shapirio, Vaananen, and Henkin in the article) use a stronger deductive system than the standard first-order deductive system. These stronger deductive systems include comprehension and/or choice axioms. Henkin's method does show that the completeness theorem holds for these stronger systems, if the corresponding stronger classes of Henkin models are used instead of arbitrary Henkin models. It also shows that the completeness theorem holds for arbitrary Henkin models with the first-order deductive system (which is the one used in second-order arithmetic, which I think is the main application of the Henkin-models approach). I'll add a section on deductive systems to the article, and expand the part on Henkin semantics. CMummert 12:15, 30 November 2006 (UTC)

Done. I'm done with it for a while, so feel free to edit it further. CMummert 18:58, 30 November 2006 (UTC)

Ah, I'm pretty happy with what you added in your latest edits. Thanks. -Chinju 04:18, 1 December 2006 (UTC)

Reply on email

Thanks for your reply-hoped I'd caught up with an old teacher I quite liked. Seraphimblade 04:15, 1 December 2006 (UTC)

Kolmogorov complexity

I've remarked on the misleading character of the Mandelbrot set picture there. In my opinion it should be removed. What do you think? --CSTAR 19:38, 6 December 2006 (UTC)

I changed the caption. Let me know if you think the new description is more relevant. CMummert 20:08, 6 December 2006 (UTC)

Yes that's better, Thanks.--CSTAR 20:36, 6 December 2006 (UTC)

However, for the reasons you point out in the talk page there, I would prefer to remove the picture.--CSTAR 16:39, 7 December 2006 (UTC)

You are free to remove the image and comment on the talk page for that article if you wish. I am not offended enough by the new caption to remove the image, since other editors seem to like it. CMummert 18:00, 7 December 2006 (UTC)

I guess I'll live with it.--CSTAR 18:58, 7 December 2006 (UTC)

Reference for empty product (and empty sum)

I've given a list of eight at talk:empty product. Enjoy! Michael Hardy 00:27, 17 December 2006 (UTC)

Thanks, that list is above and beyond the call of duty. I'll move some of them to the main article. CMummert 00:41, 17 December 2006 (UTC)

Nice Work!

After seeing your handiwork on Exponentiation with regards to the 0⁰ debacle, I just wanted to say thanks. It was absolutely the right thing to do to move that material from Empty product and your presentation is flawless. And thanks for addressing my question about bullying. I'm still rather new here and I'm trying to learn the ropes. (As soon as my degree is finished, I hope to be able to dedicate more time to actual editing!) VectorPosse 01:37, 17 December 2006 (UTC)

I've also noticed your efforts at Exponentiation; thanks for your patience in dealing with this (although I wish it weren't necessary to deal with this kind of repeated obstinacy). —Steven G. Johnson 00:38, 29 December 2006 (UTC)