Talk:List of undecidable problems

	This article is within the scope of WikiProject Lists, an attempt to structure and organize all list pages on Wikipedia. If you wish to help, please visit the project page, where you can join the project and/or contribute to the discussion.ListsWikipedia:WikiProject ListsTemplate:WikiProject ListsList articles
???	This article has not yet received a rating on the project's importance scale.

Mathematics Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Untitled

What is the undecidable problem associated with Penrose tiling? - 72.58.19.66 06:36, 22 April 2006 (UTC)[reply]

Busy beaver problem

"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)[reply]

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

RE vs co-RE vs neither

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

Analysis: Equality of two real numbers (given by arithmetic expressions including exp and log)

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

Can there be “uncountably many undecidable problems” ?

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

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