Content deleted Content added
m Maintain {{Vital article}}: The article is NOT listed in any vital article list page. Tags: Manual revert Reverted |
m Maintain {{WPBS}}: 1 WikiProject template. Remove 1 deprecated parameter: field. Tag: |
||
| (11 intermediate revisions by 7 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=Mid}}
}}
== Tuple ==
Line 153 ⟶ 156:
:* 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)
| |||