Wikipedia talk:WikiProject Computer science

Feige's inequality on the sum of independent random variables

Hi, I would like to write a small article on Feige's inequality but have a few concerns. It will be a more educational extension of my Open Problem Garden entry. The inequality simply says that for non-negative independent random variables $X_{1},\ldots ,X_{n}$ with expectation bounded by $\mu$, $P\left(\sum X_{i}-\mathbf {E} \left[\sum X_{i}\right]<\delta \mu \right)\geq \min \left((1+\delta )^{-1}\delta ,1/13\right)$ and it has furthermore been conjectured that 1/13=0.0769... may be replaced with 1/e = 0.367... In comparison to other known probabilistic inequalities (e.g. Markov's inequality), the above RHS does not go to 0 as n goes to infinity. The original paper can be found at http://portal.acm.org/citation.cfm?id=1007352.1007443 .

1. Is the theorem and conjecture notable? The author is a well-respected researcher in complexity theory and the original article was presented at STOC 2004. The inequality is however not well-used. Google Schoolar reports 17 citations: http://scholar.google.com/scholar?cites=11347979119245205986 . Out of these, one probability theory paper improves the inequality (showing 1/8 instead of 1/13 when $\delta$=1, implying a general bound of 1/8 instead of 1/13). However, the entire paper is not devoted to this derivation. Two mention the inequality, proves a special case, and also reflect on a generalization of the inequality. Three extend the work but do not apply the inequality themselves. Three papers reference the work in passing. One cites but does not mention. Seven do not in fact cite the paper. Two references were duplicates. Only 50% +-25% of the papers were devoted to complexity theory.

2. How should the Wikipedia article be named? Feige simply calls it "an inequality on the sum of (nonnegative) (independent) random variables with unbounded variance". Other works do not refer to the inequality with any particular name (preferring references such as "the following inequality" or "Feige showed that"). May I simply call it Feige's inequality? If someone were to solve the conjecture or make significant work on it, one could rename the article appropriately.

—C. lorenz (talk) 21:32, 30 April 2009 (UTC)

Breadth-first search implementation at AfD

See Wikipedia:Articles for deletion/Breadth-first search implementation. As usual for AfD discussions, please leave a detailed comment explaining your opinion rather than just a keep or delete without an explanation. —David Eppstein (talk) 21:59, 12 May 2009 (UTC)

Participate in discussion

I'd like to have some more input on the discussion here. The subject is the proposed deletion of a second set of user templates connected with JavaScript. Thank you. Debresser (talk) 18:28, 19 May 2009 (UTC)

GA Sweeps invitation

This message is being sent to WikiProjects with GAs under their scope. Since August 2007, WikiProject Good Articles has been participating in GA sweeps. The process helps to ensure that articles that have passed a nomination before that date meet the GA criteria. After nearly two years, the running total has just passed the 50% mark. In order to expediate the reviewing, several changes have been made to the process. A new worklist has been created, detailing which articles are left to review. Instead of reviewing by topic, editors can consider picking and choosing whichever articles they are interested in.

We are always looking for new members to assist with reviewing the remaining articles, and since this project has GAs under its scope, it would be beneficial if any of its members could review a few articles (perhaps your project's articles). Your project's members are likely to be more knowledgeable about your topic GAs then an outside reviewer. As a result, reviewing your project's articles would improve the quality of the review in ensuring that the article meets your project's concerns on sourcing, content, and guidelines. However, members can also review any other article in the worklist to ensure it meets the GA criteria.

If any members are interested, please visit the GA sweeps page for further details and instructions in initiating a review. If you'd like to join the process, please add your name to the running total page. In addition, for every member that reviews 100 articles from the worklist or has a significant impact on the process, s/he will get an award when they reach that threshold. With ~1,300 articles left to review, we would appreciate any editors that could contribute in helping to uphold the quality of GAs. If you have any questions about the process, reviewing, or need help with a particular article, please contact me or OhanaUnited and we'll be happy to help. --Happy editing! Nehrams2020 (talk • contrib) 06:13, 20 May 2009 (UTC)

Kernighan-Lin algorithm

Kernighan-Lin redirects to Lin-Kernighan, which discusses the TSP algorithm. But in my textbook and lecture "Kernighan-Lin algorithm" means the graph partitioning algorithm, not the TSP algorithm. Which algorithm does it usually mean? Should the article Kernighan-Lin be changed to discuss the partitioning algorithm instead? Offliner (talk) 10:37, 9 June 2009 (UTC)

It's been many years since I was voted an honorary physics and math major (BTW, project page is on my watchlist, so Offliner, I'm not following your edits). AFAIK, it should be a "see also." The Kernighan-Lin algorithm is a heuristic, while TSP (traveling salesman problem) and GPP (graph partitioning problem) are targets for application of the heuristic. Neither TSP or GPP should be named for Kernighan-Lin/Lin-Kernighan or the other way around, that is, separate articles for:

• GPP
• Kernighan-Lin
• TSP

I haven't checked the articles, but somewhere in TSP there should also be discussion of TSSP (Traveling Salesman Subset-tour Problem).

   I believe K-L is currently more associated with TSP, but in any event I think it's better to keep the algorithm and "P"roblems separate. The "P"roblem articles should not be about the heuristic to solve them. Hope this helps. PetersV       TALK 14:23, 9 June 2009 (UTC)

Afterthought, there's GCP (Graph Color Problem) as well. PetersV       TALK 15:01, 9 June 2009 (UTC)

Are you saying that both the KL algorithm for TSP and the KL algorithm for GPP use the exact same heuristic? It doesn't seem that way to me. In all the books I've seen so far Kernighan-Lin algorithm means the GPP algorithm. Thus I don't think it's correct that Kernighan-Lin redirects to an article about the TSP heuristic. I think we should:

1. rename Lin-Kernighan to Kernighan-Lin heuristic for traveling salesman problem
2. create Kernighan-Lin algorithm which will contain info about the GPP algorithm
3. add a short description of that algorithm to Graph partitioning problem also
4. make Kernighan-Lin a disambig page with links to Kernighan-Lin heuristic for traveling salesman problem and Kernighan-Lin algorithm

If someone insist, we can also name Kernighan-Lin algorithm => Kernighan-Lin algorithm for graph partitioning instead for clarity. Offliner (talk) 08:28, 10 June 2009 (UTC)

I think Kernighan-Lin algorithm for graph partitioning is appropriate and we can have Kernighan-Lin algorithm with a Redirect. Point 1-4 are perfect. --Sayed Mohammad Faiz Haider Rizvi (talk) 10:34, 10 June 2009 (UTC)

I looked up some papers on Google and it seems the heuristic algorithm for TSP is usually called the Lin-Kernigahn heuristic/algorithm, while the one for GPP is usually called Kernighan-Lin heuristic/algorithm (note the order of the names.) Perharps put them at Lin–Kernighan heuristic and Kernighan–Lin algorithm and put a note at the top of both articles. —Ruud 16:13, 10 June 2009 (UTC)

The respective papers are:

• BW Kernighan, S Lin (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal.
• S Lin, BW Kernighan (1973). "An effective heuristic algorithm for the traveling-salesman problem". Operations Research.

—Ruud 16:21, 10 June 2009 (UTC)

Application of the K-L algorithm outside of its original space is where some boundaries appear to cross, doing a survey of papers. Ruud's suggestion here is the best and simplest solution. Other applications of the algorithm can be mentioned (briefly) as appropriate. PetersV       TALK 16:46, 10 June 2009 (UTC)

I've renamed the articles. Kernighan–Lin algorithm could use a bit more content. —Ruud 23:13, 10 June 2009 (UTC)

I've expanded the article with a description and pseudocode. Others are invited to check the additions for errors and other issues. Offliner (talk) 13:47, 12 June 2009 (UTC)

First-order logic

I have recently been working, with some other editors, to improve the article first-order logic. As this is an area of overlapping interest between mathematics and computer science, editors here may want to look through the article and improve any shortcomings from a CS perspective. Any feedback on this relatively long article would be appreciated, but the section on automated theorem proving may be of particular interest. — Carl (CBM · talk) 22:01, 15 June 2009 (UTC)

Consensus Please

Excessive cross-posting. Spammed to 11 WikiProjects. [1] Hans Adler 14:32, 24 June 2009 (UTC)
The following discussion has been closed. Please do not modify it.
In the article Physics of the Impossible a single editor removed material that I believe, very much enhanced this article. The other editor’s view is that the removed material was off topic. My view is that it is very much on topic. The current article is here: (current) The version which I restored is at my sub page here: (restored) Everything that was removed is related to the book. This is because, as the author writes: “The material in this book ranges over many fields and disciplines, as well as the work of many outstanding scientists.” There is a two and one half page list of the individuals, “who have graciously given their time for lengthy interviews, consultations, and interesting, stimulating conversations.” Most on this list happen to be scientists. I listed only the first 22 individuals and these are scientists. In addition, I linked their names to their biography on Wikipedia. I also listed each scientist’s fields of specialties. Many on the list in the article have more than one field of specialty (view here), and hence this reflects the breadth of knowledge contained in this book. If you look at this section in the restored article you will see what I mean. In addition, before this material was removed by the one editor, the article was much more interactive. It was also more in line with the intent of Wikipedia that that the readers (as well as the editors) have a satisfying experience with Wikipedia. One aspect of this more satisfying experience is being able to access the knowledge that is available at Wikipedia on the sciences, and, perhaps, the mathematics. So, I linked not only the names on the list, but also many of their scientific disciplines to the respective Wikipedia article. Accessing this knowledge supports the following WikiProjects and their respective portals: (there are more I am sure) WikiProject Astronomy WikiProject Books WikiProject Physics WikiProject Space WikiProject History of Science WikiProject Science WikiProject Mathematics WikiProject Technology WikiProject Computing WikiProject Computer Science WikiProject Engineering Also, there were graphics that were removed which support the article and the concepts in the book. I believe these should be restored as well. These are on the restored article page, at my sub page. The captions of the graphics show that the book is grounded in real science. If you scroll through the restored article you will see the variety of graphics. I believe these enhance the article aesthetically, as well as help to give a clearer picture of the concepts contained in the book and the article. Lastly, there were external links that were removed which reflect the concepts in the book. These external links were removed as though they were not relevant. For example, I will list some of the external links, and then the page number in the book, to which each link is related: Solar sails: pp. 152, 158 - 159, 166, 172… Space elevators: pp. 165 – 169 Black holes: 156, 232, 235 – 236… Travel at the speed of light: 159 – 161, 163 – 165, 169 – 170… Unfortunately the external links that were removed are going to have to be restored one at a time, because they cannot be cut and pasted back from the revision history without some distortion. I think these external links should also, be restored to the article. I think the bottom line is, let common sense decide. Even Wikipedia guidelines say that they are just guidelines, not letter of the law. I would appreciate a consensus on whether or not to keep the removed material. Please place your comments here: Consensus please. This is on the talk page of Physics of the Impossible. Thanks for your time Ti-30X (talk) 13:22, 24 June 2009 (UTC)

Use of 'source lang="foo"' (Syntax highlighting)

I'm against it unless it's defined in the language spec or until it's controllable via preferences. Is there a policy on this anywhere? If not, is this the right place to discuss it. Thanks! - Richfife (talk) 15:31, 3 July 2009 (UTC)

And I'm stongly against it until someone fixes the ridiculous colour scheme. :) Scheme (programming language) has plenty of examples of hard-to-read yellow-on-gray text. Haskell (programming language), on the other hand, highlights all strings with a strong green background, as if those were the most important part of the whole article. — Miym (talk) 16:05, 3 July 2009 (UTC)

You should be able to customize or disable the colouring in your personal style sheet. It could probably also be done using a "gadget" in the user preferences. I agree the default colour scheme (MediaWiki:Geshi.css) should be more readable and consistent. —Ruud 19:14, 3 July 2009 (UTC)

Sys-Con

The reliability of Sys-Con as a source is being discussed at Wikipedia:Reliable sources/Noticeboard#Sys-Con. -- Collectonian (talk · contribs) 04:48, 28 July 2009 (UTC)

Class names in bold

I noticed that many of the complexity class related pages have classes in bold. So it's PSPACE, instead of PSPACE, NP instead of NP, and so on. But then some pages don't have it this way. Should we write all complexity classes in bold wherever they appear? (Is there some policy regarding this?) --Robin (talk) 13:58, 29 July 2009 (UTC)

MOS:BOLD doesn't say anything about it, but I personally feel that having both uppercase and boldface is a bit much. —LOL ^T/_C 14:12, 29 July 2009 (UTC)

Actually, my personal opinion is that plain uppercase looks like shouting and bold uppercase looks acceptable, strangely enough. The latter also appears to be the convention used by modern authors. (Of course, the fact that they are uppercase in the first place is unfortunate, but there's nothing we can do about it.) Shreevatsa (talk) 15:09, 29 July 2009 (UTC)

I'm not sure what I prefer, but in Arora and Barak's book that you linked to, they also use capital boldface for names of problems, like SAT and Subset Sum. --Robin (talk) 19:35, 29 July 2009 (UTC)

No, for problems or languages they use capital sans-serif (non-bold): 3SAT, SUBSETSUM (except occasionally bold in text where they're actually using bold for emphasis). It's probably hard to tell on Wikipedia as the default font is sans-serif, but compare 3SAT, SUBSETSUM and 3SAT, SUBSETSUM. This means that we can't directly follow all their conventions, incidentally. Shreevatsa (talk) 20:09, 29 July 2009 (UTC)

I would prefer as little typographical mumbo-jumbo as possible. “Satisfiability” and “NP” are perfectly fine words, TCS neither needs nor deserves special considerations different from other encyclopaedic terms. NP should behave like USA, and Satisfiability like Entscheidungsproblem. (Also remember that we have very little control over Wikipedia’s appearance on various media and platform anyway.) Thore Husfeldt (talk) 07:23, 30 July 2009 (UTC)

If we decide to use NP instead of NP, there are tons of complexity articles which will have to be edited to reflect this. --Robin (talk) 14:28, 11 August 2009 (UTC)

The Compiler article

Hello! The Compiler article has an "expert" tag on it, and is Top-importance but only Start-Class. The article looks pretty factual to me, so I removed the old "disputed" tag, but I'd appreciate it if one of the self-declared Compiler Experts around here could do a quick look-over for serious problems. I think the expert tag could probably be removed, but I don't think of myself as an expert, y'know? Anyway, right, important stuff! Let's not ignore it! :) Indeterminate (talk) 09:02, 30 July 2009 (UTC)

Lambda calculus

Can someone with (at least) a graduate-level understanding of the topic take a look at the article, in particular the confusion with various typed lambda calculi; see the article's talk page for details. Pcap ping 17:31, 5 August 2009 (UTC)

Near Root Algorithm

Would someone experienced in determining how marginally notable a topic needs to be to justify an article, please have a look at Near Root Algorithm. Johnuniq (talk) 01:55, 11 August 2009 (UTC)

It seems to be exactly the Babylonian method, explained badly and without error analysis. --Robin (talk) 14:26, 11 August 2009 (UTC)

Reorganize the Computability articles

(Note: This is a cross-post from wikiproject math. The discussion has now moved to Talk:Recursion theory#Reorganize the Computability articles to keep the discussion centralized.)

We have these "general" articles:

• Computability, which incorrectly implies that computability in CS and Math are somehow disjoint. This should not be a dab or a stub!
• Computability theory (computer science), a poor quality article that focuses narrowly on automata and Turing machines (despite the name). Barely mentions lambda calculus in the history section and makes no mention of recursion theory or random access machine!!
• Model of computation, a sort of WP:DICTDEF

We also have much better articles on the important topics, recursion theory, lambda calculus, Turing machine, and random access machine; we also have a decent overview article on register machines in general.

The way I see it computability should be is a high-level intro to the often encountered equivalent models of computation: recursion theory, lambda calculus, Turing machine, and random access machine. This is along the along the outline of S. Barry Cooper's Computability Theory (see pp. 7-8), which despite being written by mathematician was quite satisfying for me as a computer scientist (despite the many misprints, and his insistence on calling RAMs URMs, but that's another matter).

Pcap ping 11:22, 13 August 2009 (UTC)

The discussion is now at Talk:Recursion theory#Reorganize the Computability article (edited note at top here) Dmcq (talk) 11:55, 14 August 2009 (UTC)

Category:Data types and Category:Type theory - crossref from WPMATH

How should Category:Data types and Category:Type theory be related to each other? See Wikipedia_talk:WikiProject_Mathematics#Category:Type_theory_and_Category:data_types

Further friction and little light now at Category Talk:Type theory. Are types in Computer Science and Mathematics different beasts? Pcap ping 10:46, 24 August 2009 (UTC)

Template categories

Just letting you know I've created: Category:Computer science templates, and Category:Computer science stub templates taking clue from Wikiproject Math. Please categorize suitable templates that you know about in those categories. Thanks, Pcap ping 04:57, 23 August 2009 (UTC)

There is a Category:Computing templates, which contains a lot of templates that rightly belong in CS templates. --Robin (talk) 13:54, 23 August 2009 (UTC)

They can be included in both. No need for a food fight. By the way, I've also created {{PL-stub}} which was sorely missing. The OOP-related stuff has so many articles that it probably should get its own stub type. Also, I've avoided tagging concurrency stubs with the PL tag. Those should probably get their own a well. Lotsa boring work. Pcap ping 14:05, 23 August 2009 (UTC)

All of those are navbox templates. Do not add them directly to Category:Computer science templates, but create Category:Computer science navbox templates if you feel like going over them. Pcap ping 14:09, 23 August 2009 (UTC)

See Category:Mathematics templates for further ideas on organizing this stuff. And, no they don't have navbox templates there, they despise them! Pcap ping 14:12, 23 August 2009 (UTC)

I thought the category was for navbox templates. It says "The pages listed in this category are meant to be navigational (navbox) templates."

About the stub template you created, aren't we supposed to first propose its creation at Wikipedia:WikiProject_Stub_sorting/Proposals? --Robin (talk) 14:54, 23 August 2009 (UTC)

See below for "asking permission". Yes, they have a few subdued "bottom of the page links templates"; compare to the gigantic ones found in most computer-related articles. The Wikipedia terminlogy in this area is also confusing, as "Navboxes" is somehow a supercategory of stub templates and all other. Perhaps calling them "see also navboxes" or "series navboxes" would be more explicit. That's why I think it's better to put them in a subcat, but I don't care much either way. Pcap ping 15:40, 23 August 2009 (UTC)

Asking permission to create stubs

I have a rather dim view of that wikiproject given the ridiculous procedural requirements listed there. They've never managed to get those requirements in the main guideline, so they're just sneaking them in through the back door by making you kowtow to them beforehand. What happens if articles in a stub category get expanded so that the number of stubs drops below their "magic" threshold for having a stub category; should the stub category be deleted and stubs up-categorized? That's just busy work to justify the existence of their project, which hasn't done much if anything for computer science articles as evidenced by the huge lump of topics in the main comp-sci stub category; not to mention that a lot of topics are listed as "computer-stubs" and what not. By the way, have you ever heard of computer languages as a topic of study? They had a silly {{compu-lang-stub}}, which I've redirected to {{PL-stub}}. Let them undo my work if they don't like it; I'm not going to ask permission. Some stub categories in the Math wikiproject plainly don't meet the requirements set out by the stubs wikiproject, but they're still around. The way I see it: if a wikiproject manages its own stub categories, "help" from the stubs project isn't needed. Pcap ping 15:29, 23 August 2009 (UTC)

See also Talk:Computer_language. Pcap ping 15:43, 23 August 2009 (UTC)

After giving it some further thought, I won't bother with stubs anymore. Basically, it's duplicated effort on top of categories. Stub "sorting" should all be done in software, i.e. with intersection of categories. That way you'd able to mark any article just with {{stub}}. No need for all the ridiculous infrastructure currently used on this wiki (have a look at the fr.wiki where there's only one stub type -- I don't know if they've activated DynamicPageList there or not). But then Wikipedia, unlike Google, is mainly based on grunt work (that rewards people with promotions in a bureaucracy) instead of good software, so I'm not holding my breath I'll see any changes. Pcap ping 17:28, 23 August 2009 (UTC)

I created a number of stub templates a few years ago (I'm pretty sure there was a {{compu-lang-stub}} back in those days.) Most of them got deleted by the stub sorting bureaucrats as the stub sorters wouldn't be able to properly differentiate between the various templates, or so I was told. This of course entirely ignored the fact that there were several people here at this project happy to properly sort the stubs. —Ruud 19:38, 24 August 2009 (UTC)

Logically every category should have a stub category associated with it. But it's not worth the hassle to create all those by hand; they should be database views, i.e. stub "sorting" should be done in software by intersecting the topic categories with a single stub category. The way things are done on Wikipedia, that's not very likely to happen. Luckily we don't need to obtain permission from WP:WikiProject Categories to create categories, but somebody is probably working to "fix" that... Pcap ping 07:33, 27 August 2009 (UTC)

A lot of articles are wrongly categorized in Category:Formal methods

See Category_talk:Formal_methods#A_lot_of_article_are_wrongly_categorized_in_this_cat. Pcap ping

Also, my rant here. Pcap ping 15:10, 23 August 2009 (UTC)

Yes, some of the people doing categorization have some trouble differentiating formal methods from formal systems. Just recategorize those articles as you come across them. At least it's not as annoying as anything remotely related to computing getting labeled as computer science. —Ruud 19:33, 24 August 2009 (UTC)

AfD input sought

Anyone's input on Wikipedia:Articles for deletion/Comparison of ABAP and Java would be appreciated. --Cybercobra (talk) 01:00, 26 August 2009 (UTC)

Category:Computer language stubs nominated for deletion

See Wikipedia:Categories_for_discussion/Log/2009_September_1#Category:Computer_language_stubs. Pcap ping 10:56, 1 September 2009 (UTC)

Also {{PL-stub}} was (rightfully) nominated for renaming at Wikipedia:Stub_types_for_deletion#.7B.7BPL-stub.7D.7D. Pcap ping 00:27, 2 September 2009 (UTC)

Computational complexity and analysis of algorithms and program optimization vs. algorithmic efficiency

I could not ignore that the last article above appears to be one giant, ad-hoc WP:CFORK of the other three, combining some issues. The terminology "algorithmic efficiency" is somewhat common in academia [2] (about 600 gbooks hits) but pales compared to "computational complexity" [3] (about 5000 gbook hits) or "analysis of algorithms (1200 hits) and about on par with "program optimization" [4]. Even then, "algorithmic efficiency" it's more of WP:DICTDEF that can refer to any number of things rather than a field of study. The citations given, as well as the frequent references to some concrete programming languages ("algorithmic efficiency" pretends to be about algorithms in the abstract), suggest that this article has mostly written by programmers with little regard for how academics consider these topics. Granted, it's going to be a monumental job merging the appropriate parts from algorithmic efficiency in computational complexity, analysis of algorithms and program optimization, depending on where a particular topic belongs. Do you guys think this should be done? Other ideas for dealing with this? Pcap ping 19:23, 1 September 2009 (UTC)

There seems to be very little content in algorithmic efficiency that would go in Computational complexity theory. The whole section on "Optimization techniques" can go in program optimization. After that, the rest can be merged with Analysis of Algos and Program Optimization, as needed. This step will take time, but might not be as bad as it looks. --Robin (talk) 03:50, 2 September 2009 (UTC)

Concrete complexity

By the way, we do not seem to have an article on this, and we should. Any volunteers? Pcap ping 19:23, 1 September 2009 (UTC)

What is Concrete complexity? Can you link me to a paper? --Robin (talk) 03:44, 2 September 2009 (UTC)

A book would be a better idea, e.g. [5] [6]. See also what W. Gasarch thinks of this area. Pcap ping 16:10, 2 September 2009 (UTC)

In depth discussion whether programming language =?= computer language

At Talk:programming language. Since the article is rated Top importance for this project, I thought you should know... Pcap ping 00:25, 2 September 2009 (UTC)

Symbolic analysis for deletion

I've nominated this and Symbolic Program Analysis for deletion. Pcap ping 22:36, 4 September 2009 (UTC)

Use of primary sources in the history section of Math/TCS articles

This thread on uses of primary source in the history sections of Math articles (at WP:WPM, of course) may be of interest to participants here because a fair number of TCS articles are of central interests to both projects, and have such sections. Pcap ping 13:31, 5 September 2009 (UTC)

Some shades of WP:OR at Algorithm#Classification

Perhaps someone can find a good source for that? All books on algorithms I'm aware of do not bother with taxonomical issues at the level that some industrious Wikipedian(s) have... Pcap ping 15:25, 7 September 2009 (UTC)

Church-Turing thesis as "unsolved problem"

We have a box in that article that proclaims, rather idiosyncratically, that it is an unsolved problem. Of course, the actual (claimed) problem is to "formalize" it so it can be "proved". Even this appears to me to be an idiosyncratic view of a few authors, as most state that the thesis is not something that can be proved because in general one needs to "quantify" over all computational models (I can give citations if anybody doubts me). So, it's somewhat questionable to have it included in Unsolved problems in computer science as well, given that most authors do not believe it to be something of a provable nature. So, the box appearing in the CTT article reflects a minority POV in my view. Any other opinions? Pcap ping 23:04, 13 September 2009 (UTC)

I think the best approach would be to first re-write Unsolved problems in computer science so that we don't have Church-Turing thesis there; the box will be easy to remove after that. And in my opinion, it is clear that the problem of formalising Church-Turing thesis does not belong to a short list of the most important open problems in all computer science. Strong claims need strong evidence; if it was a major open problem, it would be mentioned in numerous textbooks, surveys, etc., and I don't see such references in the article. — Miym (talk) 23:35, 13 September 2009 (UTC)

By the way, people might be more eager to add things like "formalising Church-Turing thesis" to Unsolved problems in computer science if the list of unsolved problems looks too short, like it desperately needs some new entries. So adding real major open problems to the list might help. See Talk:Unsolved problems in computer science#Cleanup ideas for some discussion related to expanding the list. — Miym (talk) 23:45, 13 September 2009 (UTC)