Talk:Computability theory (computer science): Difference between revisions

Revision as of 18:38, 30 October 2006

Latest revision as of 05:04, 13 July 2024

(14 intermediate revisions by 11 users not shown)

Line 1:

{{tpr}}

{{WikiProject Computer science}}

==Untitled==

__TOC__

I believe the Entscheidungsproblem was first proved unsolvable by Church, and months later by Turing. Goedel's theorems don't really talk about algorithms, so they don't directly apply. Of course, Goedel's trick of Goedel numbering and the Barber paradox is really the key to the Entscheidungsproblem and halting problem, everything else is details. --AxelBoldt

Line 271:

How is the following statement confusing? ''"Actually, these are computer programs written in general-purpose programming languages which are Turing Machines (the GP languages are, therefore, called Turing-complete), while the actual computers executing the programs are FSMs."'' I have included it into the article even before looking into the discussion to disambiguate the popular confusion: [http://groups.google.com/group/sci.math/browse_frm/thread/a19842fff35d1ca2/e7d0c7b501d31e8c?lnk=st&q=PC+fsm+turing+poll&rnum=1#e7d0c7b501d31e8c "Poll: Are PCs Turing Machines?"] Thi is the actual and vast confusion. What I see at this page proves my doubts. Please explain what is so confusing in my sentence? Peahaps it is rather wrong or inappropriate? --[[User:Javalenok|Javalenok]] 09:02, 13 June 2006 (UTC)

:I don't know what "confusion" you're referring to. Your statement is accurate, but the English is difficult to understand, and I'm not sure how much it adds in this context. [[User:Dcoetzee|Dcoetzee]] 22:30, 30 January 2008 (UTC)

== Church-Turing thesis ==

This discussion is copied from the user page.

You changed [[Church-Turing thesis]] to claim that it had been disproven. This is certainly not the case. Please feel free to discuss your changes on the talk page of the article. [[User:CMummert|CMummert]] · <small>[[User talk:CMummert|talk]]</small> 10:49, 12 April 2007 (UTC)

:The [[Church-Turing thesis]] has ''not'' been disproved. However, it needs to be stately precisely which was not done in the previous version of the article. It is very important to distinguish between computable '''functions''' and computability ('''computations''').--[[User:71.198.216.63|71.198.216.63]] 16:11, 12 April 2007 (UTC)

==Deciding a language==

I don't understand this idea. What does it mean to decide a language? [[User:Unfree|Unfree]] ([[User talk:Unfree|talk]]) 16:32, 30 January 2008 (UTC)

:To decide whether a given string is in the language or not. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 20:11, 30 January 2008 (UTC)

== Attempt to merge ==

For anyone keeping this article on their watchlist: there is currently an attempt at merging a number of articles on (non-)recursive/(un)decidable/(un)computable sets/languages/decision problems into a single, thorough article. The experiment currently sits at [[Recursive languages and sets]]. Comments are very welcome. [[User:Pichpich|Pichpich]] ([[User talk:Pichpich|talk]]) 00:43, 21 February 2008 (UTC)

== A paradoxical situation ==

This is a duplicate post from [[Talk:Algorithm#A_paradoxical_situation]]. To keep the discussion in one place, please comment there is you are interested. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 20:43, 19 March 2008 (UTC)

== Reorganize the Computability articles ==

There is a discussion currently at [[Talk:Recursion theory#Reorganize the Computability articles]] about reorganising the computability articles to get some sort of hierarchy. In particular the thinking is that [[Computability]] should be an introduction rather than a disambiguation page. [[User:Dmcq|Dmcq]] ([[User talk:Dmcq|talk]]) 11:26, 14 August 2009 (UTC)

:The reorganization is underway. The centralized discussion is at [[Talk:Recursion theory#Reorganize the Computability articles]]. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 14:52, 22 August 2009 (UTC)