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

Revision as of 00:23, 20 February 2006

Latest revision as of 05:04, 13 July 2024

(21 intermediate revisions by 17 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 45:

I think the article should be rewritten to focus more on [[computable function]]s instead of Turing machines. This should be done in most articles in the computability category. Of course Turing machines are easier to grasp then the abstract concept of computable function, but by focussing on the abstract concept we can eliminate the redundant discussion of [[lamda calculus]], [[recursive function]] and [[Church-Turing thesis]] in each computability article. I guess in many cases the proofs and theorems will get shorter too. We can always add a ''concrete'' example using Turing machines if the article gets to abstract [[User:MathMartin|MathMartin]] 23:59, 9 Nov 2004 (UTC)

:I have the opposite opinion. TM gives very intuitive and simple representation for computability. See the proofs for uncomputability of [[Busy Beaver]] functions. More of the results may be demonstarted on TM (or other programming language) examples. If you get the [[Quine (computing)|Quine]] program, it is easy to expand it to self-explorer program, and then using self-opposite behavior to proof easy non-stoping problem, Godel incompleteness theorem and other results. Such proofs are simple and don't use complex and hard for understanding mathematical notation. [[User:Skelet|Skelet]] 19:16, 7 Dec 2004 (UTC)

::I do not object to using Turing machines as examples, but as with any model, Turing machines only serve to illustrate certain points. Other points can be illustrated better using other models. My point is the main (technical) definition should be based on [[computable function]]s. But at the moment I am not able to devote any amount of time on this topic. So I guess for now things will stay as they are. [[User:MathMartin|MathMartin]] 19:30, 9 Dec 2004 (UTC)

Line 118:

--[[User:Exa|Exa]] 15:41, 22 January 2006 (UTC)

:''"It does not mean that physical machines cannot be TMs!"'' -- All the real HW pcs. are FSMs and, hence, are TMs.

:''"Every TM denotes a particular computation"'' -- The TMs are SW programs executed by particular HW FSM. --[[User:Javalenok|Javalenok]] 18:43, 9 June 2006 (UTC)

:Except inasmuch as they behave nondeterministically, desktop machines are finite state machines. You might argue that it's more useful to treat them using the theory of Turing machines, and I'd tend to agree, but in the strictest mathematical sense they aren't Turing machines.

Line 253 ⟶ 255:

:The text appears almost identical to the contribution to [http://groups.google.com/group/comp.theory/browse_thread/thread/97be4cfe4eb1821e] by Marissa Kay on Thurs, Feb 9 2006 7:48 -- [[User:PJTraill|PJTraill]] 01:11, 19 February 2006 (UTC)

::Both had the same author. The article, itself, clearly stands on its own since the arguments made in it are sufficiently self-contained and cogent to settle the issue, subsuming prior published literature on the matter, particularly in its taking into account the finiteness imposed as a result of the Bekenstein Bound, which has been neglected in the literature and is really the critical point in deciding the issue. The question of whether the universe is deterministic or not is open. The Schroedinger equation is, in fact, deterministic and state evolution under it, likewise so. Whether the apparent non-determinism associated with "collapse" is real or only epiphenonemal and deriveable from a more fundamental, and deterministic, substrate (e.g. by decoherence, consistent histories, or some other mechanism, etc.) is really the central issue of the so-called [[measurement problem]] of quantum theory and is as-of-yet unresolved. But, the question is moot anyway: non-deterministic FSM's are <i>not</i> equivalent to deterministic FSM's! This equivalence only applies to deterministic vs. non-deterministic FSA's. The non-equivalence for FSM's is readily seen by the trivial counter-example of a FSM with states {S,F}, input {X}, outputs {Y,Z}, start state S, final state F and the two transitions on input X from S to F, one transition having output Y, the other having output Z. A deterministic FSM cannot yield more than one translation for any input. This one yields the two translations for the input "X": "Y" and "Z". Therefore it is not reducible to an equivalent deterministic FSM.

== Universal Turing Machines ==

What about Universal Turing Machines? Shouldn't they be included as well? [[User:70.111.251.203|70.111.251.203]] 14:42, 7 March 2006 (UTC)

== Cleanup ==

Found use of first person. While text is clear and easy to understand, it is still bad style. [[User:210.50.201.22|210.50.201.22]] 05:35, 26 May 2006 (UTC)

If you really want to try to rewrite it without the first person, and make it even remotely close to as easy to understand, be my guest. This is a very common style for proofs. --[[User:Readams|Readams]] 15:59, 6 June 2006 (UTC)

== confusion PCs are not FSMs ==

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)