Talk:RE (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
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.
Mathematics rating:
Start Class
Mid Priority
 Field:  Foundations, logic, and set theory

What does RE have to do with complexity? Computability is the right term, no?—Preceding unsigned comment added by (talkcontribs)

See Complexity_class. RE are problems that always halts when accepting and can fail to halt when not accepting. So no upper bound can be placed on time consumption of the hardest problems in RE. Thus RE is greater than all other complexity classes. Taemyr (talk) 13:04, 22 January 2008 (UTC)


I noticed there was no article about semi-algorithms, but this page was the closest we have. Since I'm not too deeply entrenched in computability theory, I decided to redirect semi-algorithm here and put in a definition. QVVERTYVS (hm?) 12:56, 21 May 2014 (UTC)