Talk:List of undecidable problems
Add topic | This article is rated List-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
| |||||||||||||||||||||
Untitled
[edit]What is the undecidable problem associated with Penrose tiling? - 72.58.19.66 06:36, 22 April 2006 (UTC)
Busy beaver problem
[edit]"Given a number N, determine if a machine of a specified number of states will halt after N steps for some computation" is a decidable problem! (Just run the machine for N steps and see what happens.) I will fix this in a minute. Ebony Jackson (talk) 15:35, 25 May 2009 (UTC)
- While you are obviously right, I think this may just have been a wrong formulation of the problem. The decision variant of the Busy Beaver should probably be something like "Given a Number N, determine if any machine of a specified number of states exists that will stop after N steps for some input." Or perhaps also "Given a machine, decide if it is a busy beaver champion." As Σ is noncomputable, both questions should be undecidable. Then again, I am no expert, and as the list is missing uncountable many problems as it is, it is probably safer to leave out another one than to introduce a false one. X127 (talk) 00:08, 11 August 2010 (UTC)
It might be useful to note for the problems given in this list whether they are in RE or co-RE or neither. Especially some examples of problems which are not even partially decidable would be interesting. X127 (talk) 23:44, 10 August 2010 (UTC)
Analysis: Equality of two real numbers (given by arithmetic expressions including exp and log)
[edit]In a "previous version", User:D.Lazard added this as undecidable problem. However undecidability seems to be a long-standing open question. So until a credible reference is added I suggest to refrain from listing it as undecidable. — Preceding unsigned comment added by Martin Ziegler (talk • contribs) 08:45, 13 December 2013 (UTC)
Can there be “uncountably many undecidable problems” ?
[edit]In the first paragraph of this article we see: “There are uncountably many undecidable problems, so the list below is necessarily incomplete.” Note, however, that each undecidable problem has a textual description, that text strings are countable, and that therefore the undecidable problems are countable. — Preceding unsigned comment added by Bill stoddart 2 (talk • contribs) 15:52, 15 February 2017 (UTC)
- A problem need not have a textual description; in the usual terminology every set of natural numbers is a decision problem. — Carl (CBM · talk) 22:43, 15 February 2017 (UTC)