Jump to content

RE (complexity): Revision history

View logs for this page (view filter log)

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 14:5814:58, 13 May 2025 2601:240:c403:58d0:685:b380:39e0:97fd talk 7,185 bytes +20 →RE-complete: Fix Rice's theorem bullet; specify that it's partial recursive functions, because computable functions do have some decidable properties (e.g. whether f(0) = 0) undo Tag: Visual edit

curprev 07:5307:53, 10 October 2024 TTWIDEE talk contribs m 7,165 bytes 0 →RE-complete: Fixed capitalisation undo

curprev 23:3823:38, 10 June 2024 Jensep talk contribs 7,165 bytes +28 →top: added link to complement undo Tags: Mobile edit Mobile app edit Android app edit

curprev 07:2707:27, 24 August 2023 OAbot talk contribs m 7,137 bytes +17 Open access bot: doi updated in citation with #oabot. undo

curprev 01:0801:08, 17 January 2023 Citation bot talk contribs 7,120 bytes +17 Add: s2cid. | Use this bot. Report bugs. | Suggested by Smasongarrison | Category:Undecidable problems | #UCB_Category 14/20 undo

curprev 08:1908:19, 26 May 2022 LaundryPizza03 talk contribs 7,103 bytes +508 →Relations to other classes undo

curprev 14:4714:47, 25 May 2021 213.119.8.88 talk 6,595 bytes +22 No edit summary undo

curprev 11:3711:37, 7 January 2021 LaundryPizza03 talk contribs 6,573 bytes +34 added Category:Undecidable problems using HotCat undo

curprev 02:1302:13, 6 January 2021 Alexander.zw talk contribs 6,539 bytes +631 Elaborate on equivalent definition undo

curprev 04:0204:02, 29 March 2020 Wylie39 talk contribs m 5,908 bytes −36 Reverted edits by 92.6.7.172 (talk) to last version by Citation bot undo Tags: Rollback SWViewer [1.3]
curprev 04:0204:02, 29 March 2020 92.6.7.172 talk 5,944 bytes +36 No edit summary undo Tags: Mobile edit Mobile web edit

curprev 08:5908:59, 24 March 2020 Citation bot talk contribs m 5,908 bytes −18 Alter: template type. Add: eprint, class, year. Removed URL that duplicated unique identifier. Removed accessdate with no specified URL. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by User:Headbomb | via #UCB_webform undo

curprev 00:2500:25, 25 February 2020 AHusain3141 talk contribs 5,926 bytes +466 MIP* undo

curprev 18:4218:42, 19 January 2020 Jamgoodman talk contribs 5,460 bytes −4 →RE-complete: tense undo

curprev 13:2513:25, 16 January 2020 Bellowhead678 talk contribs m 5,464 bytes +1 Conversely,the->Conversely, the - Fix a typo in one click undo Tags: Mobile edit Mobile web edit Advanced mobile edit

curprev 17:2517:25, 19 November 2019 Chrisahn talk contribs 5,463 bytes +2 →RE-complete: Trying to make it clearer undo Tags: Mobile edit Mobile web edit Advanced mobile edit
curprev 17:2317:23, 19 November 2019 Chrisahn talk contribs 5,461 bytes +56 →RE-complete: Description of Post correspondence problem was incorrect. This should fix it. I hope the sentence is reasonably clear... undo Tags: Mobile edit Mobile web edit Advanced mobile edit

curprev 03:1203:12, 7 November 2019 InternetArchiveBot talk contribs 5,405 bytes +146 Bluelink 1 book for verifiability.) #IABot (v2.0) (GreenC bot undo

curprev 08:2508:25, 17 May 2019 Ynof talk contribs m 5,259 bytes +12 Spelling undo

curprev 20:3220:32, 16 May 2019 Joel Brennan talk contribs m 5,247 bytes +1 →co-RE-complete undo
curprev 20:3220:32, 16 May 2019 Joel Brennan talk contribs m 5,246 bytes +1 →RE-complete undo

curprev 22:5022:50, 29 April 2019 Rockstone35 talk contribs 5,245 bytes +97 →Relations to other classes undo
curprev 22:4622:46, 29 April 2019 Rockstone35 talk contribs 5,148 bytes +382 →Relations to other classes: (added information about NRNC class) undo

curprev 21:2821:28, 31 January 2019 145.109.34.55 talk 4,766 bytes −59 →RE-complete: removed false claim: "[Re-complete] problems are nonrecursive. ". This is not true, by the Church-Turing Thesis something is computable iff it is computed by a recursive function. I think the confusion might have been between partial and total recursive functions. undo

curprev 12:2312:23, 30 August 2018 RussBot talk contribs m 4,825 bytes +17 Robot: fix links to disambiguation page Validity undo

curprev 18:2518:25, 17 June 2018 No identd talk contribs 4,808 bytes +28 →See also: Added Polymorphic recursion undo Tag: 2017 wikitext editor
curprev 18:2118:21, 17 June 2018 No identd talk contribs 4,780 bytes +125 →See also: Added the Knuth-Bendix completion 'algorithm' (Not actually an algorithm!), the Risch algorithm & the semidecidability section of the Decidability article undo Tag: 2017 wikitext editor

curprev 22:2222:22, 19 August 2017 Quinton Feldberg talk contribs m 4,655 bytes +12 fix citations undo

curprev 07:4007:40, 3 June 2015 Download talk contribs 4,643 bytes +2 →See also: bullet undo

curprev 12:3312:33, 16 April 2015 Qwertyus talk contribs 4,641 bytes +267 be more precise/verbose about the required behavior on 'no' instances undo

curprev 12:5312:53, 21 May 2014 Qwertyus talk contribs 4,374 bytes +632 define semialgorithm too undo

curprev 16:2816:28, 12 June 2013 2001:718:2:80b:223:8bff:fe30:f662 talk 3,742 bytes +143 →Relations to other classes: added the reason for R = RE ∩ coRE undo
curprev 16:2316:23, 12 June 2013 2001:718:2:80b:223:8bff:fe30:f662 talk 3,599 bytes +19 →Relations to other classes: internal link added undo
curprev 16:2116:21, 12 June 2013 2001:718:2:80b:223:8bff:fe30:f662 talk 3,580 bytes +19 →Relations to other classes: citation needed undo

curprev 18:3518:35, 28 February 2013 Addbot talk contribs m 3,561 bytes −112 Bot: Migrating 4 interwiki links, now provided by Wikidata on d:q905621 (Report Errors) undo

curprev 02:0902:09, 30 August 2012 Fox2k11 talk contribs 3,673 bytes −29 Reverted edit(s) by 69.41.92.40 Using STiki undo

curprev 23:4723:47, 29 August 2012 69.41.92.40 talk 3,702 bytes +29 No edit summary undo

curprev 18:3718:37, 24 March 2012 David Eppstein talk contribs m 3,673 bytes +34 →RE-complete: doi undo
curprev 18:3618:36, 24 March 2012 David Eppstein talk contribs m 3,639 bytes +219 →RE-complete: templatize ref undo

curprev 21:1921:19, 18 March 2011 WikitanvirBot talk contribs m 3,420 bytes +22 r2.7.1) (robot Adding: zh:RE (複雜度) undo

curprev 16:3916:39, 21 December 2010 Alvillo talk contribs 3,398 bytes +58 No edit summary undo
curprev 12:5212:52, 21 December 2010 Alvillo talk contribs 3,340 bytes +136 →co-RE-complete undo
curprev 12:5212:52, 21 December 2010 Alvillo talk contribs 3,204 bytes −97 →RE-complete undo

curprev 18:2618:26, 28 September 2010 Justin W Smith talk contribs 3,301 bytes +19 →Relations to other classes: Clarification undo

curprev 22:3522:35, 31 July 2010 Algebraist talk contribs m 3,282 bytes −1 rm whitespace undo

curprev 18:5718:57, 11 July 2010 CRGreathouse talk contribs m 3,283 bytes +35 Disambiguated: recursive → recursive language, recursive function → Computable function using Dab solver undo

curprev 23:0723:07, 5 June 2010 Luckas-bot talk contribs m 3,248 bytes +33 robot Adding: es:RE (clase de complejidad) undo

curprev 09:2309:23, 24 November 2009 Tea2min talk contribs m 3,215 bytes +24 Linked to complexity class and decision problem undo

curprev 20:5420:54, 23 November 2009 RobinK talk contribs 3,191 bytes +230 Reverted to revision 314029540 by RobinK; rv. (TW) undo
curprev 17:4917:49, 23 November 2009 199.212.250.155 talk 2,961 bytes −25 →co-RE-complete undo Tag: possible test edits

Retrieved from "https://en.wikipedia.org/wiki/RE_(complexity)"