Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computability
Search options not deleted
user 109
Computability theory a.k.a. recursion theory.
19
votes
A simple decision problem whose decidability is not known
The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory.
Query containment takes as input two queries $Q_1$ a …
- 19.2k
10
votes
1
answer
390
views
Computational consequences of Friedman's (unprovable) Upper Shift Fixed Point theorem?
The USFP Theorem seems to be a $\Pi^1_1$ statement, so it might be "close enough" to computability (such as checking non-isomorphism of automatic structures), to impact theoretical computer science. …
- 19.2k
12
votes
Accepted
Is one definition of the word paradox, "something that can be used to prove the halting prob...
It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments. Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the m …
- 19.2k
20
votes
3
answers
3k
views
How do models of hypercomputation overcome the Halting Problem?
Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access …
- 19.2k
12
votes
3
answers
294
views
Is there a natural restriction of VO logic which captures P or NP?
The paper
Lauri Hella and José María Turull-Torres,
Computing queries with higher-order logics,
TCS 355 197–214,
2006.
doi: 10.1016/j.tcs.2006.01.009
proposes logic VO, variable-order logic. This …
- 19.2k