Talk:Computability theory

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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)