Talk:Computably enumerable set: Difference between revisions

Revision as of 19:10, 8 August 2008

Latest revision as of 23:49, 8 March 2024

(32 intermediate revisions by 14 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|vital=yes|1=

{{WikiProject Mathematics|priority=Mid}}

}}

== Tuple ==

Line 49 ⟶ 53:

[[User:CMummert|CMummert]] 20:25, 14 July 2006 (UTC)

To add to the the above, the first paragraph in the "Remarks" section seems to contradict the opening definition of recursively enumerable sets.

[[User:Bandar|kapil]] ([[User talk:Bandar|talk]]) 06:53, 23 March 2010 (UTC)

:How ya figure? --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 07:42, 23 March 2010 (UTC)

== Equivalent definitions? ==

Line 101 ⟶ 110:

::I didn't mean to suggest including tons of examples but I think a few examples would help a lot. Thanks. [[User:Wanderer57|Wanderer57]] ([[User talk:Wanderer57|talk]]) 19:10, 8 August 2008 (UTC)

:::The answer to your question is "yes" (well, except I'd quibble on "positive", since we seem to be allowing 0), and your program witnesses that the set of all natural numbers is r.e. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 19:14, 8 August 2008 (UTC)

::::Thanks. Can you suggest a program that witnesses that the set of natural numbers that are multiples of 7 are r.e., because the ___domain of the function is that set? [[User:Wanderer57|Wanderer57]] ([[User talk:Wanderer57|talk]]) 19:28, 8 August 2008 (UTC)

:::::Trovatore's original function witnesses that. If the input is a multiple of 7, the program halts. Otherwise, it does not halt. So the ___domain (set of values for which it halts) is exactly the set of multiples of 7. This is a [[partial function]].

:::::The term "co-range" is not used in recursion theory; it's a category-theory term. I think it was added here in an attempt to clarify for category theorists which meaning of "___domain" is intended. See [[___domain (mathematics)]] &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 19:46, 8 August 2008 (UTC)

(unindent) The word "___domain" is ambiguous. According to [[Binary relation]], "''A binary relation R is usually defined as an ordered triple (X, Y, G) where X and Y are arbitrary sets (or classes), and G is a subset of the Cartesian product X × Y. The sets X and Y are called the ___domain and codomain, respectively, of the relation, and G is called its graph.''". Sometimes it is used to mean the set of things which might be considered as inputs to the function &mdash; in our case, the ___domain in that sense of a partial recursive function is always the natural numbers. Other times, ___domain (second sense) is used to mean the set of things within the ___domain (first sense) which when input to the function yields a value. This is what I was calling the "co-range" (for want of a better word) because the "range" of a function is the set of values which it outputs while the "co-___domain" is the set of things within which the range (image of the ___domain) is located, that is, in our case, the natural numbers (again). [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 06:00, 9 August 2008 (UTC)

:Sure, ''___domain'' is ambiguous in general, but it's not ambiguous in recursion theory or descriptive set theory. In those fields it has a standard meaning. On the other hand ''co-range'' I have never heard of — Carl says it's a category-theory term, which is possible, but in my limited experience with category theory I've never come across it. We aren't supposed to make up language here. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 07:22, 9 August 2008 (UTC)

::Thanks to all of you for your help in uderstanding this. As I said, I'm starting pretty far back.

::As a general comment, I think complex terminology is a huge barrier to comprehension of this subject area. Both the article itself and some of the above discussion illustrate that.

::For example, in the first sentence of the article, even before an r.e. set is defined, the reader is given an alternate name for the subject (i.e., computability theory, traditionally called recursion theory) and four alternatives for the term r.e. (i.e., computably enumerable, semidecidable, provable and Turing-recognizable). IMO this is packing too much information into one sentence.

::Thanks, [[User:Wanderer57|Wanderer57]] ([[User talk:Wanderer57|talk]]) 18:53, 9 August 2008 (UTC)

:::It is hard to avoid doing that. We need to identify the subject of the article quickly by whatever name a reader might know it. Once you realize that these are synonyms, you can ignore the ones you do not recognize on your first reading of the article. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 06:41, 10 August 2008 (UTC)

::::Thanks. I wonder if an initial statement in italics might be better, by taking the synonyms out of the defining sentence. E.g.,

::::''(Computably enumerable, semidecidable, provable and Turing-recognizable are synonyms for recursively enumerable.)''

::::Another question -- suppose a lookup table is created by picking a million numbers from a random number table, and an algorithm is created that halts only when given an input that is in the lookup table. Would that algorithm determine an r.e. set? [[User:Wanderer57|Wanderer57]] ([[User talk:Wanderer57|talk]]) 15:45, 10 August 2008 (UTC)

:::::Yes. Every finite (or co-finite) set of natural numbers is recursively enumerable. Indeed, they are recursive. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 16:13, 10 August 2008 (UTC)

=="Algorithm"==

Article says:

:* There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s₁, s₂, s₃, ... . If necessary, this algorithm may run forever.

I have requested discussion at

:[[Talk:Algorithm characterizations#can_an_algorithm_produce_infinite_output.3F]]

of whether this is a legitimate use of the word "algorithm", which I thought had to produce at most finite output. [[Special:Contributions/66.127.52.47|66.127.52.47]] ([[User talk:66.127.52.47|talk]]) 21:20, 20 March 2010 (UTC)

== Universal recursively enumerable set ==

Strangely, I do not see here a universal recursively enumerable set. [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 17:52, 17 February 2018 (UTC)

:It is not defined here (and I have forgotten the definition), but I believe that these two examples listed in the section on examples would qualify:

:* Given a [[Gödel numbering]] <math>\phi</math> of the computable functions, the set <math>\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}</math> (where <math>\langle i,x \rangle</math> is the [[Cantor pairing function]] and <math>\phi_i(x)\downarrow</math> indicates <math>\phi_i(x)</math> is defined) is recursively enumerable (cf. picture for a fixed ''x''). This set encodes the [[halting problem]] as it describes the input parameters for which each [[Turing machine]] halts.

:* Given a Gödel numbering <math>\phi</math> of the computable functions, the set <math>\lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace</math> is recursively enumerable. This set encodes the problem of deciding a function value.

:[[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 12:39, 18 February 2018 (UTC)

== Should move to [[computably enumerable set]] ==

I have tagged [[computably enumerable set]] as G6 -- this page should be moved there per [[WP:NOUN]]. I think this is pretty cut and dried; I hope we don't need an RM. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 05:53, 29 July 2022 (UTC)

== 2021 renaming ==

Detailed here: [[Wikipedia_talk:WikiProject_Mathematics/Archive/2021/Jun#Proposal: change terminology from "recursive" to "computable"]]. --[[User:Dan Polansky|Dan Polansky]] ([[User talk:Dan Polansky|talk]]) 14:55, 10 October 2023 (UTC)

== Origin of enumerable = partial? ==

Instinctively, I would expect ’enumerable’ to mean that I can make an enumeration, in which case ‘computably enumerable’ ought to mean that there is some algorithm which computes the next item in the sequence for me. Instead it seems to mean the opposite: adding this attribute to a term ''weakens'' it so that I can never be sure what is the next item in a sequence, unless it is just the numerical successor! ‘Partial’ I can see why it should be like that, but for ‘enumerable’ it comes across as a mystery. What is the historical background for this choice of terminology? (That would be a useful addition to the article.) [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 16:45, 25 January 2024 (UTC)

Okay, found the explanation — in the alternative definition "The set S is the range of a total computable function, or empty.", which in at least {{cite book |last1=Mendelson |first1=Elliott |title=Introduction to Mathematical Logic |date=1987 |publisher=Wadsworth & Brooks/Cole |isbn=0-534-06624-0 |page=259 |edition=3rd}} is taken as the primary definition. The proof that this implies "is the ___domain of a partial recursive function" is straightforward, but the converse is '''very''' difficult. [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 17:33, 25 January 2024 (UTC)

:This isn't the place to discuss it, but actually the proof of the converse is not conceptually difficult. There might be a few details to get past, but the idea is straightforward. If you want to know more, please ask a question on [[WP:RD/Math]]. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 19:17, 25 January 2024 (UTC)