This is the
talk page for discussing improvements to the
Computability theory article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||
|
![]() | Note about previous edit history On 2009-8-22, the previous edit history of Computability theory was moved to Talk:Computability theory/OldHistory, and then Recursion theory was moved to Computability theory. See also Talk:Computability_theory_(computer_science). |
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)
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)
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)
Why is this page a double dab? Shouldn't computable be its own dab page? Pcap ping 17:14, 13 August 2009 (UTC)
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)
Computability theorists have an odd sense of "weak" and "strong".
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:
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
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)
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)
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)
<dl><dt>Foobar</dt></dl>
- for things which aren't definition lists is "fine"? 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)
Definition list markup is not broken; MOS uses it itself. The questions to be asked are
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)
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:
{{
citation}}
: External link in |title=
(
help)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). Bill Wvbailey ( talk) 23:06, 23 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)
This article uses the following reference style (I should know, I established it):
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)
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)
…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)
Terms like "very recent" will become dated, and you will never know when. JMK ( talk) 11:59, 6 January 2016 (UTC)
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.
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:
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).
Cheers.— InternetArchiveBot ( Report bug) 20:18, 11 August 2017 (UTC)
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)
This is the
talk page for discussing improvements to the
Computability theory article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||
|
![]() | Note about previous edit history On 2009-8-22, the previous edit history of Computability theory was moved to Talk:Computability theory/OldHistory, and then Recursion theory was moved to Computability theory. See also Talk:Computability_theory_(computer_science). |
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)
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)
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)
Why is this page a double dab? Shouldn't computable be its own dab page? Pcap ping 17:14, 13 August 2009 (UTC)
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)
Computability theorists have an odd sense of "weak" and "strong".
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:
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
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)
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)
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)
<dl><dt>Foobar</dt></dl>
- for things which aren't definition lists is "fine"? 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)
Definition list markup is not broken; MOS uses it itself. The questions to be asked are
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)
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:
{{
citation}}
: External link in |title=
(
help)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). Bill Wvbailey ( talk) 23:06, 23 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)
This article uses the following reference style (I should know, I established it):
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)
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)
…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)
Terms like "very recent" will become dated, and you will never know when. JMK ( talk) 11:59, 6 January 2016 (UTC)
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.
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:
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).
Cheers.— InternetArchiveBot ( Report bug) 20:18, 11 August 2017 (UTC)
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)