Talk:Computability theory

Should this page even exist?

I was checking out this disambiguation page with a view towards disambiguating the links, and I wonder: should this page exist? I am sure that there are some set theorists who have used the term "computability theory" to describe recursion theory, but I'm willing to bet that if I were to go through the links to this page all, or almost all, should point to computability theory (computer science). Now, of course I could be wrong which is why I am asking here. Any comments? --Deville (Talk) 12:33, 8 February 2006 (UTC)

I'd prefer an unequal disambiguation to computability theory (computer science), but only if User:Trovatore is fine with it as well. —Ruud 12:45, 8 February 2006 (UTC)

Really I think they should probably never have been split; I'd prefer a re-merge at some point. At the time of the split the article was written too much from the computer science perspective. That ought to have been corrected, but it's tricky to do right. --Trovatore 13:59, 8 February 2006 (UTC)

This really should just be one page, there's no point in seperating the two pages as they discuss the same topic just from different points of view. —Preceding unsigned comment added by 85.180.67.188 (talk) 00:50, 11 January 2008 (UTC)

Do we agree that among the pioneers of computability theory is Kleene, that Moschovakis is an eminence grise, Soare, Ted Slaman, and Rod Downey are established current figures, Denis Hirschfeldt and Joel Hamkins are up-and-comers? If so, we're talking about the same subject, and we should really have one article. The problem with the computability theory (computer science) article is it spends too much time defining computability and establishing that it's distinct from non-computability, and not enough outlining current areas of research. The basic exposition should be shipped off to, say, the computable function article or the Turing machine article (it may already be there), and linked to from the main article with a brief blurb. There should then be sections for various current areas of research, each with a blurb and a link to a main article. They would include complexity theory, structure of the Turing degrees, randomness theory (not sure that's what it's called; I'm talking about the kind of stuff Downey and Hirschfeldt do), and effective descriptive set theory. And other things that y'all think of (I'm not really sure what computer scientists who call themselves computability theorists actually study). --Trovatore 14:39, 8 February 2006 (UTC)

I don't think there is anything wrong with two articles because of the different emphasis. But please: they are the same subject. My book Computability and Unsolvability (1958 and still around thanks to Dover) is certainly recursion theory. There's really no need for a disambiguation page. Soare has been on a campaign to use "computable" not "recursive". Recursive functions are computable functions - they are the same thing. Martin Davis 22:34, 13 September 2006 (UTC)

Of course you're right. This is largely my fault (the other part of the fault would belong to those who wrote the computability theory article before I got to it). The article at that time was very boring and had a lot of repetitive stuff (duplicative of other articles, to boot) about what was computable and what wasn't; I didn't feel comfortable weeding it out the way it needed to be weeded, to make room for more interesting material. Maybe you'd like to take a crack at it? --Trovatore 23:51, 13 September 2006 (UTC)

Ambiguous links to this page

There's about 100 "ambiguous" links to this page. Maybe one of you could take a look and see how they should be resolved? Here's the list. Thanks! Ewlyahoocom 06:16, 9 October 2007 (UTC)

Double dab?

Why is this page a double dab? Shouldn't computable be its own dab page? Pcap ping 17:14, 13 August 2009 (UTC)

Reorganization

The page Recursion theory was moved here, as part of a larger reorganization. Centralized discussion is at Talk:Recursion theory#Reorganize the Computability articles. — Carl (CBM · talk) 14:53, 22 August 2009 (UTC)

I have started the reorganization. Let's keep the discussion in the same location, Talk:Recursion theory#Reorganize the Computability articles, even though recursion theory is a redirect now. — Carl (CBM · talk) 15:20, 22 August 2009 (UTC)

Weak and strong

Computability theorists have an odd sense of "weak" and "strong".

• First, there is a very old usage of "strong reducibility" to mean "many-one reducibility", due to Shapiro. I think this has vanished now, but it is in Davis 1958.
• Second, there is a classical use documented in Rogers 1967, p 138, where Turing and truth-table reductions are "the weak reducibilities" and many-one and one-one reductions are "the strong reducibilities".

In modern computability terminology, if ≤_A implies ≤_B then A is said to be stronger than B. Equivalently, as Odifreddi, "Strong reducibilities", p. 43, says:

"Every degree of a weaker reducibility is the union of degrees of stronger reducibilities"

This may seem backwards if you think of reducibilities as equivalence relations first; but if you think of them as computational processes, a stronger reducibility carries with it more information than a weaker reducibility. So from weak to strong, we have

arithmetical ← Turing ← truth-table ← many-one

I tried to fix this in the article just now, but I also have to think about the terminology to get it right. One difficulty is that computability theorists generally study particular reducibilities, rather than the general theory of reducibilites. I found a paper online that gave a general definition of "stronger reducibility" [1] but I don't think it's a very good reference for this article. I would look in Odifreddi's book but I don't have a copy at hand. — Carl (CBM · talk) 22:09, 6 April 2010 (UTC)

PS There are also "strong" and "weak" reducibilites corresponding to Medvedev degrees and Muchnik degrees of sets of reals, respectively. This is a different setting; I just wanted to complete my taxonomy of the terms. — Carl (CBM · talk) 22:12, 6 April 2010 (UTC)

Say what?

The second paragraph of the article begins with:

      The basic questions addressed by recursion theory are "What does it mean for a function from the natural numbers to themselves to be computable?"  ...

We seem to have a grammatical glitch here. What is the intent? — Preceding unsigned comment added by Toddcs (talk • contribs) 19:07, 31 March 2011 (UTC)

What is the glitch? — Carl (CBM · talk) 20:19, 31 March 2011 (UTC)

Headings

I've just accidentally used rollback, rather than undo; so couldn't leave an edit summary. My reason was to restore MOS-compliant, semantic and accessible sub-headings to the references section, instead of broken definition-list markup. Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 10:38, 22 April 2011 (UTC)

The previous markup seemed fine. Could you explain what you mean by "MOS compliant"? — Carl (CBM · talk) 10:59, 22 April 2011 (UTC)

The MoS mandates that headings should use proper, nested heading markup ("Spaced or unspaced multiple equal signs are the style markup for headings"). Can you say in what way the use of definition list markup - specifically <dl><dt>Foobar</dt></dl> - for things which aren't definition lists is "fine"? And explain why you have again reverted, with no informative edit summary? Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 15:22, 22 April 2011 (UTC)

I did not revert. Please check the edit history carefully before making such claims. — Carl (CBM · talk) 17:42, 22 April 2011 (UTC)

My apologies; I mistook you for Ruud Koot. Care to answer my other point? Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 21:18, 22 April 2011 (UTC)

I would prefer not to switch to multicolumn references here. The normal way people format bibliographies in math books is to have one column of references, not two. Two narrow columns are much harder to read, and there's no lack of space in a browser window. — Carl (CBM · talk) 13:09, 22 April 2011 (UTC)

Two things should be separated:

1: You replaced ===Undergraduate level texts=== by ;Undergraduate level texts, et cetera.

2: You removed {{refbegin|2}} and {{refend}}.

The first thing is what Pigsonthewing commented on. It does not help you to get one column of references, so it is better to leave it the old way. Pigsonthewing showed that the MOS requires this.

The second thing is what helps you to get multicolumn references. On my screen, two columns makes it easier to read, one column is more difficult. There might be something in the Manual of Style (MOS) about this, but I don't know where. --EdgeNavidad (Talk · Contribs) 16:13, 22 April 2011 (UTC)

As above, I did not revert the section heading change. However, I don't think those are really subsection headings in the first place. They are simply bold text that is meant to group the references in the single section "references". That is subtly different than making three subsections; instead it is a single section consisting of three lists, each of which has a title. — Carl (CBM · talk) 17:56, 22 April 2011 (UTC)

Definition list markup is not broken; MOS uses it itself. The questions to be asked are

• Is the list going to be too busy if every bold-face entry has a line break after it? (Not germane here; the line breaks exist either way.)
• Do we want the individual subsection headers in the Table of Contents? (Probably not; few people are going to want to click on them directly.)

In short, this is a close and unimportant issue, to be decided solely on the basis of the reader's convenience. Septentrionalis PMAnderson 19:48, 22 April 2011 (UTC)

{od}I agree that "Definition list markup is not broken" and did not claim otherwise; however the partial definition list markup used on this article is. The cited MoS section does not use definition list markup. Bold text that is meant to group [things]" is a heading. Headings, per accessibility guidelines, should use heading markup. Accessibility is not "unimportant" Inaccessibility is very inconvenient so some. To what aspect of this do you both object? Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 21:18, 22 April 2011 (UTC)

Fair enough. That is a third question:

• Does the advantage of increased accessibility for screen readers, which serve a minority, outweigh the disadvantage of unnecessary links in the ToC, which affects everybody, including those with screen readers?

  Quite honestly, I'm not sure. It depends, I think, on how screen readers generally parse bold text. Septentrionalis PMAnderson 22:12, 22 April 2011 (UTC)

You haven't demonstrated that there are "unnecessary links in the ToC", much less that they "[affect] everybody, including those with screen readers". Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 22:22, 22 April 2011 (UTC)

I haven't demonstrated anything - but is there a case that anybody would want to click on these subsections? As for the second question: exaggerated TOCs (let us say, as a reductio ad absurdam, 100 lines of table) would be a large cost to anybody; a screen-reader, which will read all those lines, would increase that cost. The three or four more lines involved here are lesser, but proportionate costs. Septentrionalis PMAnderson 22:39, 22 April 2011 (UTC)

I've offered evidenced concerns about accessibility issues, backed by international standards to overcome them. If all you can offer are implausible, hypothetical scenarios, then we're done. Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 23:26, 22 April 2011 (UTC)

No, you've offered a quotation from the Manual of Style, some rhetoric about the importance of accessibility (with which, in general, I agree), and no indication how severe the accessibility issues are (or, indeed, what exactly they consist of). This is the point at which you can present actual evidence to a reasonably receptive audience; please do so. Septentrionalis PMAnderson 00:25, 23 April 2011 (UTC)

Apologies; I'm confusing this debate with others on the same topic, in recent days, elsewhere, to which you were not party. See WCAG guidelines and this YouTube video: http://www.youtube.com/watch?v=AmUPhEVWu_E Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 13:41, 23 April 2011 (UTC)

According to the YouTube video, "the headings on the page can give you a very good idea what the author wanted to stand out". This page does, of course, use HTML headings, which are in the TOC. The question is whether we want the three lists inside the "references" section to stand out on their own in the TOC. I don't think there is any reason for them to be in the TOC, and someone with a screen reader will still be able to find the references by listening to the TOC. — Carl (CBM · talk) 13:52, 23 April 2011 (UTC)

No, this is very much not a question about the TOC. Most web pages, as referred to in that video have no TOC. We use headings to make things "stand out" on the page (and are currently abusing broken definition list markup to do so). We also use headings to make our articles navigable (by ordinary users, assistive technology users, and search bots). If we get the headings right, and the TOC is thus wrong, then we need to fix the way the TOC is built, not break the headings. This is also no longer a matter about just this article; I propose we move they debate to the MoS or Accessibility talk pages. Andy Mabbett (User:Pigsonthewing); Andy's talk; Andy's edits 14:35, 23 April 2011 (UTC)

Discussing it at the MOS is fine, but I think that the issue of the TOC is also important. A screen reader can navigate to the "References" section here regardless, so I think the accessibility problem is exaggerated. It's not as if the entire page has no HTML header tags at all (and just uses CSS to style headings in span or div tags), which is the situation that makes screen reader use difficult. — Carl (CBM · talk) 15:36, 23 April 2011 (UTC)

The MOS section that you quoted is explicity about section headings, by the way: Wikipedia:Manual_of_Style#Section_headings. I don't think anyone is arguing against using the standard markup with equal signs for these. But the divisions in the references section here are not section headings, but something subtly different. — Carl (CBM · talk) 15:53, 23 April 2011 (UTC)

References located in collections

Apart from the usefulness of alphabetization, it seems strange to include a paper as a separate entity that can be found in a collection. In this instanceThe Undecidable is the collection. If the refs were to list the papers under the collection, then they would look like the following:

• Burgin, M. and Klinger, A. "Experience, Generations, and Limits in Machine Learning." Theoretical Computer Science v. 317, No. 1/3, 2004, pp. 71–91
• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9

• A. Church, 1936a. "An unsolvable problem of elementary number theory." American Journal of Mathematics v. 58, pp. 345–363. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Church, 1936b. "A note on the Entscheidungsproblem." Journal of Symbolic Logic v. 1, n. 1, and v. 3, n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.
• E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• E. Post, 1947. "Recursive unsolvability of a problem of Thue." Journal of Symbolic Logic v. 12, pp. 1–11. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Turing, 1937. "On computable numbers, with an application to the Entscheidungsproblem." Proceedings of the London Mathematics Society, ser. 2 v. 42, pp. 230–265. Corrections ibid. v. 43 (1937) pp. 544–546. Reprinted in "The Undecidable", M. Davis ed., 1965. PDF from comlab.ox.ac.uk
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.

• R. M. Friedberg, 1958. "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition." The Journal of Symbolic Logic, v. 23, pp. 309–316.
• E. M. Gold, 1967. "Language identification in the limit". Information and Control, volume 10, pages 447–474.
• L. Harrington and R. I. Soare, 1991. "Post's Program and incomplete recursively enumerable sets", Proceedings of the National Academy of Sciences of the USA, volume 88, pages 10242—10246.
• C. Jockusch jr, "Semirecursive sets and positive reducibility", Trans. Amer. Math. Soc. 137 (1968) 420-436
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability." Annals of Mathematics v. 2 n. 59, 379–407.
• J. Myhill, 1956. "The lattice of recursively enumerable sets." The Journal of Symbolic Logic, v. 21, pp. 215–220.
• Shore, Richard A.; Slaman, Theodore A. (1999), "Defining the Turing jump", Mathematical Research Letters, 6: 711–722, ISSN 1073-2780, MR 1739227 {{citation}}: External link in |title= (help)
• T. Slaman and W. H. Woodin, 1986. "Definability in the Turing degrees." Illinois J. Math. v. 30 n. 2, pp. 320–334.
• R. I. Soare, 1974. "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets." Annals of Mathematics, v. 100, pp. 80–120.

To make this good, I'd have to go through the various papers and find out where they're located in The Undecidable (not a problem). (My apologies to all if this has been argued over already with a consensus to just list alphabetically). BillWvbailey (talk) 23:06, 23 April 2011 (UTC)

It's quite unusual to group articles by the collection/journal/etc. they have been published in, in bibliogrpahies. In particular, this collection seems to be a collection of reprints of previously published papers. This makes the approach somewhat infeasible as it would not form a tree-structure. In these cases I would list either the whole collection, or some/all of the papers contained within it separately, or perhaps even both, but not in such a hierarchy. —Ruud 23:20, 23 April 2011 (UTC)

I prefer to cite the individual papers when the citation is for a scientific reason, that is, when it's actually to convey information about the subject. I feel less strongly about citing collections like The Undecidable, but for the sake of an encyclopedia article I can see some benefit in listing it for readers who may realize it's a useful purchase. Still, I like to have the papers alphabetized by author, not by editor of a collection. For example, if I cited Enderton's article from the Handbook of Mathematical Logic I would want it to sort under "E", not under "B" for the editor Jon Barwise. — Carl (CBM · talk) 00:53, 24 April 2011 (UTC)

Based on the above, let's just leave the listing as it appears now. Bill Wvbailey (talk) 14:26, 24 April 2011 (UTC)

Reference style

This article uses the following reference style (I should know, I established it):

• Print references use Harvard references
• Parenthetical remarks and non-print references (e.g. mailing lists, conference webpages, etc.) use footnotes.

This is a style used by some academic journals, as well, which will not allow "unpublished" sources to be in the references section (since they will not be in libraries), but will allow them to be mentioned in footnotes. — Carl (CBM · talk) 22:16, 2 April 2013 (UTC)

This archaic citation style is no longer allowed in WP since 2020 (per WP:PAREN). I have therefore started to convert it to sfn-style. --Matthiaspaul (talk) 17:45, 2 August 2022 (UTC)

I recognize the unfortunate outcome of the RFC, but it really isn't necessary to call it "archaic". --Trovatore (talk) 17:46, 2 August 2022 (UTC)

After trying for an hour

To find a way to make this article useful to students, I have given up. Lede contains content that appears superficially, and only in the lede. Paragraph after paragraph, section after section, content appears that if sourced, is ambiguous (misstating year, lacking page numbers, etc.), but is more often unsourced synthesis, or possible OR. I am very sorry to hear that this is considered "B class". There is nothing to be done, but to return to the reliable EB. 71.239.87.100 (talk) 05:51, 2 February 2015 (UTC)

Please consider adding the byline

…to this article, "A essay written in largest part by User:CBM and User:Frank_Stephan between June 2006 and May 2007." so that readers can address its veracity based on authorship, since it is essentially unverifiable content for lack of inline citations, page numbers of books referenced, etc. Or, perhaps there is a tag that says "Trust Us", that we could append to the top, for that is what is expected of this and other articles that lack the scholarly sourcing that would allow readers to check individual ideas against sources. Do as you see fit. The article is in any case, useless for any serious educational purpose. 71.239.87.100 (talk) 06:52, 2 February 2015 (UTC)

Very recent

Terms like "very recent" will become dated, and you will never know when. JMK (talk) 11:59, 6 January 2016 (UTC)

"Predates and predetermines"

Turing's work did not "predetermine" modern computers, but different versions were constructed in several locations independently of Turing's work (as any modern history book on computing will tell). Even more importantly, Charles Babbage's programmable Analytical Engine would have been Turing complete, so Turing's work certainly did not "predate" computers. Babbage's work happened almost a hundred years earlier.

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Computability theory. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20090125120159/http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html to http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:18, 11 August 2017 (UTC)

Change in terminology: "recursive" to "computable"

There was consensus on the WikiProject Math (discussion here) that "computable" is a preferable alternative to the outdated, ambiguous "recursive" (in reference to computability/recursion theory). Therefore, articles in this category should generally use the term "computable X" rather than "recursive X". Exceptions should be made when "recursive" is still the popular name for the concept, e.g. Primitive recursive, μ-recursive, Kleene's recursion theorem. --Jordan Mitchell Barrett (talk) 22:54, 26 April 2021 (UTC)