Talk:Computable function

Should this be merged with Recursive function? --Saforrest 00:27, 27 January 2006 (UTC)

Well imho you should make it clear already on the rec.func. page that a "recursive function" is not the thing that most (unmathematical) people would first think it is, i.e. a function that references itself. --Sigmundur

Circularity of Definitions

Isn't this definition of a computable function:

A partial function $f:\subseteq \mathbb {N} \to \mathbb {N}$ is called computable if the graph of $f$ is a recursively enumerable set.

circular with the definition of a recursively enumerable set:

A countable set S is called recursively enumerable if there exists a partial computable function $f:\mathbb {N} \to S$ such that $S$ is the range of $f$? --Michael Stone 00:24, 11 March 2006 (UTC)

The circularity is resolved in practice by defining either computable function or c.e. set directly in terms of Turing machines or some other class of computing devices. The wikipedia artcles that use the word recursive seem to do this. --CMummert 02:14, 20 March 2006 (UTC)

Merge

This article is redundant with recursive function and they should be merged. I don't really care whether the merged article is here or at recursive function, but definitely it's wrong to have two articles, since by the definitions given in each article, the two sets of functions are provably coextensive.

It would be theoretically possible to have an article at computable function for functions that are informally computable, and to put the information about the formally-defined class of functions at recursive function, with a note that Church's thesis is the (unformalizable, and therefore unprovable) claim that the two classes of functions are coextensive. But I don't think that would be a good idea, given the trend, started by Robert I. Soare, to use "computable" for the formal notion. --Trovatore 00:47, 11 March 2006 (UTC)

• JA: Keep separate, with the expectation that we'll probably end up needing an introductory article and an advanced article on the same subject, computable function serving best for the intro, and recursive function or recursive partial function (which some sticklers are getting more stickly about of late) for the set-jets. Jon Awbrey 04:48, 11 March 2006 (UTC)
  • If there must be a split along those lines (an extreme measure that I doubt is justified in this case), then the names should be something like computable function and computable functions for beginners (like special relativity for beginners). There's no reason to prefer the name computable function for the proposed intro article, especially given the Soare-inspired change in language. --Trovatore 04:54, 11 March 2006 (UTC)

• JA: I don't care about the latter issue. It is simply that beginners are likely to be comfortable with computable and search there first, while they are likely either to (1) have many mis-pre-conceptions about what recursive means, that have to be gradually disabused, or (2) be put-off by the remoteness of the term from general intuitions. So the reasons are purely psychological. Jon Awbrey 05:01, 11 March 2006 (UTC)
  • Divisions of articles based on "level" are not well looked on. A more accessible introduction to the common article may be needed. That's no justification for making an arbitrary distinction between terms considered synonymous in the literature. --Trovatore 05:16, 11 March 2006 (UTC)

• JA: That's kind of why I'd avoid the explicit condescension of an X (primer) designation. But however things are looked on in theory, I have to take notice of what I've seen happen, willye nillye, but repeatedly in practice, and that is the sort of sorting out that I mention. I said it was my expectation, based on experience, but don't take my prediction for it, create an article with a precision title, like Recursive partial function -- you see Computable function is already the sort of misnomer that could only be tolerated in an informal introduction -- and see what sort of bees gather round. Jon Awbrey 05:26, 11 March 2006 (UTC)
  • "Computable function" is a standard term; misnomer or not, it's established, and has a completely precise meaning, exactly and provably coextensive with "recursive function" (partial v. total, mutatis mutandis). It's not our role to decide what standard usages are misnomers. I mildly prefer computable function for the common article but won't fight about it; if other editors want it at recursive function or even recursive partial function I could live with that. --Trovatore 05:36, 11 March 2006 (UTC)

• JA: No problem with the usage in the proper context. As a string in a formal language is can of course be defined precisely. As a lexeme in the English language it has the advantage of sounding more familiar, but as such it also has misleading connotations, that can be swept under the rug in the first part of an intro discussion, at the appropriate point explaining that a computablefunction is not of necessity a function. It's just a little nicer to have a more analytic syntax of terminology in a more formal discussion. Jon Awbrey 05:48, 11 March 2006 (UTC)
  • As I say, if you want it at recursive partial function and others support you, fine. There should still be just one article. In this scenario computable function would redirect to recursive partial function. A well-written lead section that eases the n00bs into the subject gently would be a nice addition, if you were moved to write it. --Trovatore 05:53, 11 March 2006 (UTC)

• JA: Well, I'll just be repeating things you didn't hear the 1st and 2nd times, so I'll leave it for now. When a theory prevents you from seeing what actually happens, then there's a problem there. Jon Awbrey 06:16, 11 March 2006 (UTC)
  • It does sometimes happen that articles get split along those lines. Doesn't usually work out well. That's what actually happens. --Trovatore 06:21, 11 March 2006 (UTC)

• If you do merge, let me recommend that you use computable instead of recursive throguhout. SInce a very influential article by Soare, almost every researcher in computability theory (in mathematical logic) has changed their terminology. See http://citeseer.ist.psu.edu/315828.html and http://weblog.fortnow.com/2004/02/is-it-recursive-computable-or.html --CMummert 02:21, 20 March 2006 (UTC)

• Keep separate - these articles are not about the same thing. Discussion of whether a function is computable is a different issue to whether it is a recursive function - and is also outside the scope of an article on recursive functions. QmunkE 10:01, 1 June 2006 (UTC)

• Keep separate - Recursive functions are a whole topic on their own, placing it in computable function doesn't make a lot of sense, as programmer I can be interested in recursive functions but not necessarily in computable functions since all functions you program are computable. --Lodev 17:42, 13 June 2006 (UTC)

• The set of computable functions is not a rigorously defined set. It's an intuitive notion. The Church-Turing thesis states that Turing Machine computability is equivalent to computability, and it's easy to prove that the set of *Turing-computible* functions is the same as the set of recursive functions. It takes a lot of work to equate computable functions with recursive functions, so the two articles ought to remain separate. Perphaps we could have a disambiguation page between "computable" and "Turing-computable"? *

• Keep separate - this article is about mu-recursive functions, which happen to be able to express exactly the computable functions. But Turing machines, the lambda-calculus and so on can express exactly the computable functions too. I think they should all have separate topics, as I can't see a reason to pick mu-recursive functions as a definition of the computable functions. Nick8325 18:35, 14 June 2006 (UTC)

• I am late in the debate but I think it needs additional discussion. Several of the previous posts seem to beleive that either computable function is not formally defined or think that it is defined but somehow different than recursive function. This is simply not true. In contemporary literature, the phrases recursive function and computable function mean exactly the same thing, and that is a function computable by one of the several equivalent formalizations of computability (Turing machines, register machines, Kleene's general recursive functions, etc.). I suggest the following layout of the articles here:

Computable function could describe the concept of a computable function including a brief discussion of the several models of computation with links to their detailed pages.

Recursive function could be a disambiguation page between computable functions and μ-recursive functions, that is, the closure of the primitive recursive functions under minimization. The stuff that is currently in Recursive function could be the foundation for the article on μ-recursive functions. I see that currently mu-recursive function is a pointer to recursive function, which I would like to reverse.

CMummert 20:23, 14 July 2006 (UTC)

Functions which are not computable

I have problems finding any info (on Wikipedia) about functions which are not computable. Now, it could be there exists an article about such a topic and that I should just look harder, but if it is so, the I think it should be linked from "See also" section of this article. If not, what a shame, lets write one :-) --Dijxtra 09:18, 7 April 2006 (UTC)

Rewrite as of 2006-7-16

I rewrote and significantly extended the article today. I tried to keep it balanced between Recursion theory and Computability theory (computer science). I also tried to leave in anything that was already there, to the extent possible. I made the examples of uncomputable functions more explicit, per the comment higher on the talk page. CMummert 23:33, 16 July 2006 (UTC)

First, I need to emphasize that I am a new learner in this field and I am reading this article from a pure mathematical point of view. As I finish the article, I still don't get a clue as to what the precised mathematical definition is for computable function. Is it that any function that maps an n-tuple of natural numbers into a natural number is considered a computable function? In the following, I want to quote some statements from the article and give my comments on them. "Computable functions can be used to discuss computability without refering to any concrete model of computation such as Turing machines or register machines. Their definition, however, must make some reference to some specific model of computation." My comments: It appears from the second statement that you cannot define computability without first knowing what model you are talking about. If this is the case, why shouldn't we be talking about Turing Machines computable or Register Machines computable instead of talking about computable functions in general. Why doesn't the author simply make it clear that there is no such thing as computable function in general? "Equivalently, this thesis states that any function which has an algorithm is computable." My comments: What is the mathematical definition for algorithm? Does this statement imply that a function that is not computable today may be computable some day when an algorithm is found for it? (Note: You can define algorithm as a finite procedure but then how would you define finite procedure mathematically?). Finally, I believe that we'd better have a precised mathematical definition for any object that we have to deal with if we are to be able to resolve many of the important issues in this field (e.g. P vs NP). CBKAtTopsails 11/29/2006

You may have missed the section titled Definition and in particular the following sentences:

There are many equivalent ways to define the class of computable functions. For concreteness, the remainder of this article will assume that computable functions have been defined as those partial functions that can be calculated by a Turing machine.

This is a perfectly standard and formal definition of the computable functions. As for algorithms, there are two links here to the main article on that subject. CMummert 17:20, 29 November 2006 (UTC)

I went back to read the article again and I still couldn't find a definition based on which mathematical work can be performed. The basic question is do we or do we not have a precise mathematical definition for computable function on this web? If so, where is it? I must stress again that I am pretty new in this field and my interest in this stuff was solely motivated by the curiosity about a mathematical solution to the P vs NP problem. I do not know why things are treated the way they are and whether or not there are any clearly defined objectives to accomplish and therefore I don't quite understand why so much time was spent on debating the separating and merging of topics instead of providing more precise definitions for terminologies and more rigorous treatment of the concepts. I do feel that things are very loosely tied in this field. CBKAtTopsails 11/30/2006

A computable function is a function that can be computed by a Turing machine. This is the same as saying that the function is a mu recursive function. The article says this. CMummert 13:04, 30 November 2006

First, thank you for your courtesy of responding. It is now my understanding based on your comment that computable function = mu recursive function. On that basis, I went into the article of Mu-recursive function. In this article, Mu-recursive function is defined as follows: It is a function that maps a finite tuple of natural numbers into a single natural number and it is a member of a set of functions ( Let's call it C )that satifies the following conditions: (i) The set contains the initial functions (1), (2), (3) and (ii) The set is closed under operations (4), (5) & (6). I would appreciate it if you can clarify the following for me: (a) With respect to operation (4) (Composition of Operator), what are the functions g_i's? Are they simply arbitrary elements from C? Apparently, given a set of g_i's there are infinitely many ways of defining h. So, my second question is : Is h also an arbitrary function taken from C? Does closeness here means that if h and the g_i's belong to C, then f belongs to C. Finally, I notice a little contradiction about the function h. The article first writes h(x₁,....,x_k) and then h(g₁,.....,g_m). This will result in conflicting definitions for h if m is not equal to k. (b) With respect to operation (5) (Primitive Recursion Operator), what are g and h? Are they also arbitrary functions taken from C? Why does the article write g(x₁,....,x_k) and then g(x₂,...,x_k)? Does it mean that the domain of g contain both k-tuples and (k-1)-tuples? If so, g cannot belong to C. (Same question for h). Finally, does "closed under primitive recursion operator" in this case means if g and h belong to C, then f belongs to C. If so, how can f have 0 as the first argument (0 is not a natural number). Furthermore, f is not well defined because we don't know how to compute f(y,x₂,....,x_k) given only g(x₁,....,x_k) and h(y,z,x₁,....,x_k). (c) With respect to operation (6) (Mu Operator), first, a little inconsistency about the function Muyf. Muyf(y, x₁,.....,x_k) clearly indicates that the function has (k+1) arguments but the article says "whose arguments are x₁,....,x_k. It is not clear to me what the precise definition is for Mu. I can only take a guess (from what I read) and my guess is the following (Correct me if I am wrong): Given a function f from C whose domain consists of (k+1)-tuples and given a k-tuple, (x₁,.....,x_k), if there exists a y such that f(0, x₁,....,x_k), f(1, x₁,......,x_k),............f(y,x₁,.....x_k) are defined and that f(y,x₁,.....,x_k)=0 then Muyf(x₁,....x_k)=y. However, under this definition, "f(0,x₁,.....,x_k) is defined." immediately disqualifies f to be a member of C because 0 is not a natural number. Furthermore, how can I prove that if f is from C, then Muyf belongs to C? CBKAtTopsails (11/30/2006)

Thank you for pointing out those typos in the Mu-recursive function article. However, it would have been better, if you had put your comments on the talk page for that article itself. Or you could just fix the inconsistencies yourself. Also, please separate your comments into one paragraph per problem instead of putting them together into one long run-on paragraph (which makes it difficult for me to read it and go back and forth to the article with fixes).JRSpriggs 04:31, 1 December 2006 (UTC) P.S. Zero IS a natural number.

When I typed my comments in the edit box, I did have separate paragraphs for each comment. I don't know why it came out the way it looks after I saved the page. Maybe you can offer some help on this. Do you have written instructions on how to use this edit box? CBKAtTopsails (12/1/2006).

One other comment. Presumably, I can go back to the Mu Recursive Function article to do more reading about the article and the discussion about that article but my original plan was to do some research on computable functions. I still have some doubts in my mind whether computability should be equated to recursiveness. If this topic is to be made a separate topic from the Mu Recursive Function, shouldn't it have its own definition? Why do we have two different names? I am interested in knowing whether there is a consensus in this field on how computability should be defined. CBKAtTopsails (12/1/2006).

Yes, there is consensus about how computability should be defined. In the early 20th century, several different "models of computation" were independently developed. These include lambda calculus, Turing machines, general recursive functions, mu recursive functions, Post machines, and others. After much work, it was found that all of these models give rise to exactly the same class of computable functions. The name "computable function", as used in this article, refers to a function that is computable in any (equivalently, all) of the models of computation just listed. The reasons that consensus favors this definition are

1. The fact that so many equivalent models were independently constructed.
2. The fact that no convincing example of a stronger model of computation has been presented, over a period of 70+ years.

In this article, we formally define the computable functions to be those computable by a Turing machine, which is a common way of defining them. Then we point out that there are other, equivalent definitions. The purpose of talking about "computable functions" is to avoid talking about the particular model of computation as much as possible. CMummert 18:23, 1 December 2006 (UTC)

The edit program tries to remove excess spaces and do word-wrapping. So if you really want to start a new paragraph, you must leave a blank line in between. You may put one or more colons, ":", at the beginning of a line (indicating the desired degree of indentation).

• An asterisk, "*", at the beginning of the line produces this effect.

1. A number sign, "#", at the beginning produces this effect.

A semicolon, ";", at the beginning produces this effect.

• Colon followed by asterisk does this. I hope that this helps you. JRSpriggs 11:18, 2 December 2006 (UTC)

A Problem and a Suggestion

The problem with equating the computable functions with the mu-recursive or Turing-computable functions is that the former (and probably the latter, depending upon whether you take the output of a Turing machine to be a numeral or a number) can only have sets of natural numbers as their range; so if we equate computability with recursive function-hood or Turing-computability, goedel numbering functions (or their inverses), for example, cannot be computable (since the range of one of them will be a set of strings of some alphabet), though they clearly are computable in the intuitive sense.

I propose that we not equate computable functions with any well-defined class of functions of natural numbers anywhere in the article. We should leave the discussion, warts and all, in terms of "algorithms," "finite procedures," etc., and e.g. note explicitly that the Church-Turing thesis is plausible only when restricted to functions f from subsets of N^N to N.

That being said, cleaning up all the articles conceptually related to this one would be a pain in the ass. But if there are no objections I'd volunteer to do this one, leaving intact as much as possible. --Futonchild 19:34, 1 March 2007 (UTC)

The problem with your suggestion is that it contradicts the way that the subject is treated in the real world. Computable functions are equated with Turing computable functions, because that is their definition. Godel numbering functions are not computable. Pick any textbook on computability theory and look at the the definition that it gives. The article on algorithms is the place to discuss algorithms as a distinct concept from computable functions. CMummert · talk 20:26, 1 March 2007 (UTC)

From the entry Computability and Complexity in the Stanford Online Encyclopedia of Philosophy, written by Neil Immerman at UMass:

In this way, we can list out all theorems, i.e., exactly all the valid formulas of first-order logic, can be listed out by a simple mechanical procedure. More precisely, the set of valid formulas is the range of a computable function. In modern terminology we say that the set of valid formulas of first-order logic is recursively enumerable (r.e.).

Obviously he's described an effective procedure for enumerating the set of valid formulas of FOL. From this he concludes that the set is the range of a "computable function." If the range of a computable function must be a set of natural numbers, then the function he's described couldn't possibly be computable.

When, in a given context, you're talking about functions from and to natural numbers, it's natural to understand "computable" as "mu-recursive" or whatever. But there's no reason not to recognize other types of functions--say, ones whose range is a set of formulas of the language of FOL--as being "computable" in exactly the sense in which recursive functions are. Not only is it natural to call such functions "computable," but evidently they are recognized as such by people working in computer science.

P.S. this is the first place I looked. I don't have access to any of my books at the moment, but I'm confident they also recognize such functions as computable (though not, strictly speaking, recursive). --Futonchild 21:51, 1 March 2007 (UTC)

That article follows the alternate and common convention of defining computability with Turing machines that manipulate strings of symbols, rather than with functions that manipulate numbers. The definition of computable number-theoretic functions via Turing machines uses similar conventions, because a Turing machine can't literally accept or output a natural number. There is no difference between "computable" and "recursive" in contemporary usage. I encourage you to find "your books" and read them. I can recommend some decent introductory books if you don't already have any. CMummert · talk 22:14, 1 March 2007 (UTC)

I don't understand. Was Immerman wrong to call the formula-enumerating function "computable," according to standard usage? If not, then computable functions (according to standard usage) needn't have a subset of N as their range. If so, well...that'd be surprising to me. Especially since, in this quote, we appear to have a counterexample to the claim that your understanding of "computable"(= recursive) is the standard one. --Futonchild 22:40, 1 March 2007 (UTC)

It is computable in the sense that there is a Turing machine with an appropriate (large) tape language that can produce the formulas on its tape. But it is not common to work with Turing machines with arbitrary tape languages; the most common models of computation are Turing machines with binary tape languages (used in complexity theory) and computable functions that directly manipulate natural numbers (common in recursion theory). Pretty much every book on computability theory is going to select one of these two when the formal definition of computability is given. Immerman was being sloppy informal in his writing, and you are taking what he wrote as some sort of formal definition. Immerman even says "With this definition, the Recursive functions are exactly the same as the set of partial functions computable by the Lambda calculus, by Kleene Formal systems, by Markov algorithms, by Post machines, and by Turing machines." CMummert · talk 22:54, 1 March 2007 (UTC)

Well there is clearly some tension here in Immerman's (and, I suspect, others') notion of a computable function. Say we were to point it out to him. What do you think Immerman would say? That, strictly speaking, the function that enumerates the valid sentences of FOL is not computable? Or that, strictly speaking, it is not all computable functions, but rather those computable functions that go from and to natural numbers, that are mu-recursive? I believe he (and others) would opt for the latter alternative. I.e., that Church's Thesis, stated as:

Every computable function is mu-recursive

...is implausible, once it's pointed out that there are intuitively computable functions whose range is not a subset of N, whereas the range of every mu-recursive function is a subset of N. What's sloppy is this statement of Church's Thesis. It could be more precisely and plausibly stated as the thesis that

Every computable function from n-tuples of natural numbers to N is mu-recursive.

If Church's Thesis isn't given the latter interpretation, it's simply implausible. There is no reason to think that every intuitively computable function must have a subset of N as its range. --Futonchild 23:49, 1 March 2007 (UTC)

This article is not about functions that are computable in some intuitive sense - that is what the article on algorithms is about. This article is about the functions that are formally defined as the "computable functions" using some formal model of computation. Interpretations of Church's thesis are not relevant to this formal definition. The phrase that mathematicians contemporarily use to mean what you seem to mean by "computable" (the intuitive idea of computability apart from formal definition) is "effectively calculable". CMummert · talk 00:17, 2 March 2007 (UTC)

I just found this at The Church-Turing Thesis entry, also in the Stanford Online Ecyclopedia, written by Jack Copeland:

This, then, is the "working hypothesis" that, in effect, Church proposed:

Church's thesis:

A function of positive integers is effectively calculable only if recursive.

...and:

Church used the (informal) expression ‘effectively calculable’ to indicate that there is an effective method for calculating the values of the function. He proposed that we

define the notion ... of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers).

These seem to support what I said above, that the class of computable functions, in the standard sense, is wider than the class of recursive functions. --Futonchild 00:23, 2 March 2007 (UTC)

In my experience, it's more commonly "computable" or "effectively computable" than "effectively calculable." In fact I'm not sure I've ever come across the latter. --Futonchild 00:23, 2 March 2007 (UTC)

You have just come across "effectively calculable" in the quote above. What experience are you relying on when you say "computable functions, in the standard sense"? I assure you that if you would check some books in computability theory they will confirm the explanation given in the introduction to this article. I have done my best to explain the matter; I don't see how continued discussion here is going to help if you are unwilling to actually check some references. CMummert · talk 00:54, 2 March 2007 (UTC)

Touche! All the same, "computable" is often used to mean what Church means by "effectively calculable." From the aforementioned article by Copeland:

In this connection, it is important to remember that in the technical literature the word ‘computable’ is often tied by definition to effective calculability. Thus a function is said to be computable if and only if there is an effective procedure for determining its values. Accordingly, a common formulation of the Church-Turing thesis in the technical literature and in textbooks is:

All computable functions are computable by Turing machine.

...where I think by "Turing machine" he means "idealized numeral manipulator" and not a certain kind of function. And I just now received an offprint of an article forthcoming in the Notre Dame Journal of Formal Logic in which the first sentence reads:

Church’s thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive.

(I'm not sure the author would be too psyched to know that I was quoting from the offprint, so I'm not going to give you his name).

I wonder: were you educated outside of the United States? Could this be a regional difference? Even if so, I think my original proposal was sound: the article on Computable function should present and clearly distinguish the intuitive notion from the ersatz formal definitions, and discuss the relationship between them. Doesn't that sound useful? I can't see what would be wrong with that. --Futonchild 01:16, 2 March 2007 (UTC)

The article already discusses this in two different sections: Characteristics of computable functions and Church-Turing thesis. You (and everyone else) are free to edit them. But please respect the focus of this article, which is on the formal definition of computable functions in computability theory, not specifically about algorithms or the Church-Turing thesis, which have separate articles. In other words, this article is about the functions that were traditionally called "recursive functions" in computability theory and have since come to be called "computable functions", so that the article recursive function could be a redirect page. CMummert · talk 01:38, 2 March 2007 (UTC)

Well, I didn't want to edit it unilaterally and get into a re-editing cycle like I got into with (your friend?) Trovatore. But ok I'm going to edit the Computable function page. Thanks for taking the time to discuss. --Futonchild 02:25, 2 March 2007 (UTC) (P.S. I responded to your comment on Trovatore's page, if you're interested.)

Please read the article carefully first so that you don't just insert duplicate information. The article already covers things like formal languages, the Church-Turing thesis, etc. that you seem interested in adding. It will also help if you consult published works before editing, because in the end agreement with published works is the criteria WP uses to determine article content. There is a longer bibliography in the recursion theory article. CMummert · talk 03:25, 2 March 2007 (UTC)

minor point

I'm not quite sure what a better phrasing should be but

Enderton goes on to list several requirements that are not made of the procedure for a computable function:

seems awkward or even inaccurate . If I get a chance I'll try to think about something better.

An Error Either in an Example or in Church's thesis

From the description of Church's Thesis.

“There must be exact instructions (i.e. a program), finite in length, for the procedure.”

“If the procedure is given a k-tuple x in the domain of f, then after a finite number of discrete steps the procedure must terminate and produce f(x).”

“If the procedure is given a k-tuple x which is not in the domain of f, then the procedure might go on forever, never halting. Or it might get stuck at some point, but it must not pretend to produce a value for f at x.”

Later on, an example of a computable function ...

The function f such that f(n) = 1 if there is a sequence of n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable.

If I am to take the rendition of Church's thesis on face value, this example seems wrong. So, if for a certain n, call it m, there is no sequence of m 5s in the expansion of pi, then (1) the function is defined at m and (2) the procedure will continue ad infinitum without producing a result. This contradicts the second statement, above. Church's thesis, as described here, says nothing about the procedure going on forever when given an input which _is_ in the domain of f. It only speaks, in the third part, of going on forever if given an input which is _not_ in the domain of f. So, I think that the example should be:

The function f whose domain is {n in the Natural numbers | there is a sequence of n consecutive fives in the decimal expansion of pi} and which is defined to be 1 on that domain, is computable.

Could someone please either correct this function of correct Church's thesis? —Preceding unsigned comment added by 72.74.113.222 (talk) 05:50, 7 September 2007 (UTC)

I'm afraid it's clearly computable in classical logic; it's just that we don't know what the computation is. Let N be the largest number of consecutive 5's in the decimal expansion of π, (with ∞ being a possible value for N). Then f(n) is 1 if n ≤ N, and 0 otherwise. — Arthur Rubin | (talk) 08:19, 7 September 2007 (UTC)

I see this was already in the article, explained better than I did. I don't know what the anon is talking about. — Arthur Rubin | (talk) 12:25, 7 September 2007 (UTC)

This is a standard example in courses on computability theory, and the anon has made the mental mistake that many people do when learning this. Most people think of a computable function intensionally - it is linked to a particular algorithm to compute it. The anon is saying that since the obvious attempt at an algorithm to compute this function doesn't work, it is therefore not computable. But the actual definition of a computable function is extensional - a function is computable if there is any algorithm that computes it, even if that algorithm is "trying to compute a different function". In this situation, the algorithm that computes this function is just a short program that makes no mention of π. That's because, extensionally, this function is only barely related to π. — Carl (CBM · talk) 13:00, 7 September 2007 (UTC)

Someone asked for a citation. This example is an exercise in Fundamentals of Mathematical Logic, Hinman, 2005 - see 4.2.48 on p. 340. This example is actually extremely common in texts, as it is immediately accessible to students and the problem of whether there are arbitrarily long runs of a single digit in π hasn't been solved yet. — Carl (CBM · talk) 13:26, 7 September 2007 (UTC)

Correctness of Busy Beaver Example

I think the claim about the busy beaver function: "every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is (trivially) computable" is false.
At the very least, it's contradictory to the claim on the busy beaver page that "there is a true-but-unprovable sentence of the form 'Σ(10↑↑10) = n' "
As, if the fist statement were true, one should "trivially" be able to compute the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(10↑↑10) thus "trivially" computing Σ(10↑↑10).
Also, as a general note, I think articles should avoid claims that something is "(trivially) computable" unless a simple proof is given or referenced.

— Preceding unsigned comment added by 18.111.124.28 (talk • contribs) 18:25, 4 October 2011

Every finite sequence of natural numbers is indeed trivially computable. For example, the program can just have a list of the numbers, and if you ask it if n is the mth number in the list, it just looks it up and says yes or no. --Trovatore (talk) 19:42, 4 October 2011 (UTC)

Trovatore, the busy beaver numbers are eventually independent of set theory by Chaitin's theorem, aren't they? For example, the authors here: http://www.scottaaronson.com/busybeaver.pdf exhibit a 7918-state Turing machine that ZFC can't prove runs forever, but that a slightly-augmented version of ZFC can, which seems to me to suggest that BB(7918) cannot be defined in ZFC. We might do well to mention that limitation, here, if someone can find appropriate sources, since it means the phrase "the finite sequence {BB(1), BB(2), ..., BB(7918)}" cannot be assigned a definition (in computer science based on ZFC, anyway), and hence cannot be computable, even though any given sequence of 7918 natural numbers is of course computable. — Preceding unsigned comment added by 50.58.96.2 (talk) 15:48, 21 August 2017 (UTC)

There is no problem defining the sequence, and ZFC is irrelevant here. It's true that there is no particular number that ZFC proves equal to BB(7918) (assuming you've reported this correctly; I haven't checked that point, but if it's not 7918 it's something else). But that has nothing at all to do with being able to define the sequence. A deep-dive into this is kind of beyond the scope of this page; if you'd care to ask a question at WP:RD/Math or WP:RD/Computing I'd be happy to say more. --Trovatore (talk) 18:59, 21 August 2017 (UTC)

This is all correct. For each n, in ZFC we can define "the sequence of the first n Busy Beaver numbers and we can prove that finite sequence is computable. It is true that ZFC cannot prove the exact values of the sequence but it can prove the sequence to be computable. By analogy, ZFC proves that the infinite sequence that is all 1s if the Continuum Hypothesis holds and all 0s otherwise is computable, even though ZFC cannot prove the exact values of the sequence. — Carl (CBM · talk) 23:05, 21 August 2017 (UTC)

Uncomputable and not incomputable

Please note that most standard texts refer to these functions as UNcomputable and not INcomputable. — Preceding unsigned comment added by 132.205.45.13 (talk) 17:08, 23 August 2012 (UTC)

Good catch. I hadn't noticed that it said incomputable in two spots. --Trovatore (talk) 21:47, 23 August 2012 (UTC)

Paragraph makes no sense

"Similarly, most subsets of the natural numbers are not computable. The halting problem was the first such set to be constructed. The Entscheidungsproblem, proposed by David Hilbert, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations."

The first sentence is hard enough to interpret (do you mean finite or infinite subsets of the natural numbers?). But then you move on to "the halting problem was the first such set to be constructed". This makes no sense. Firstly, whatever you mean by that statement needs to be unpacked at the bare minimum (if not just thrown out.). Secondly, on it's face, problems are not sets. The halting problem is about computer programs that could be implemented in any turing complete language. A function that determines halting of arbitrary programs for any language in this class of languages would lead to paradox. You in no way make it clear how this relates to any uncomputable subset of the natural numbers. But then you jump to entscheidungsproblem and you're talking about statements encoded as natural numbers. How does the uncomputability of some statements encoded as natural numbers imply the uncomputability of some (finite? infinite?) subsets of natural numbers? This whole paragraph makes no sense and needs to be rewritten (or maybe just thrown out). Comiscuous (talk) 06:39, 20 January 2022 (UTC)

There are only countably many computable sets of natural numbers, and there are cardinality of the continuum-many sets of natural numbers period. Therefore most sets of natural numbers are not computable. Is that clearer? Would you propose some clearer text for the article, if not?

(As to the "finite or infinite sets?" query — you can include the finite sets if you want to; there are only countably many of them so they don't affect the argument either way.)

You're right, the halting problem per se is not a set of natural numbers, but the set of Turing machines that halt is a set of natural numbers, or might as well be (you can give each Turing machine a natural-number code in an effective way).

I'm not trying to dismiss you here. It would be great to improve the readability of the text. Could you take a crack at making some concrete suggestions, after digesting my response? --Trovatore (talk) 06:54, 20 January 2022 (UTC)