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-theory
Search options not deleted
user 1946
computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on …
80
votes
Accepted
Will this Turing machine find a proof of its halting?
It is a very nice question. The answer is yes, the machine will find a proof of its own halting nature, and it will halt when it does so.
I claim this is a consequence of Löb's theorem. Let $M$ be a T …
- 236k
76
votes
6
answers
9k
views
Which graphs are Cayley graphs?
Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main …
- 236k
56
votes
Accepted
Can a group be a universal Turing machine?
Update. Here is a more direct construction. (See edit history for previous version.)
There is such a universal computable group as you request. Let $F$
be the free group on infinitely many generators …
- 236k
52
votes
What are the most attractive Turing undecidable problems in mathematics?
The Word Problem for groups is undecidable. This is the problem, given a finite group presentation and a word, to decide if that word is the group identity in that presentation. The problem is undecid …
46
votes
What are the most attractive Turing undecidable problems in mathematics?
The Halting Problem, the mother of them all.
44
votes
What are the most attractive Turing undecidable problems in mathematics?
The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The pr …
43
votes
4
answers
3k
views
What do we know about the computable surreal numbers?
The surreal numbers are built up in a natural iterative process, by which at any ordinal stage, if one has two sets of surreal numbers $L$ and $R$, with every number $x_L$ in $L$ strictly below every …
- 236k
39
votes
Decidability of chess on an infinite board
There is a positive solution for the decidability of the mate-in-$n$ version of the problem.
Many of us are familiar with the White to mate in 3
variety of chess problems, and we may consider the na …
- 236k
37
votes
Accepted
Is the theory of categories decidable?
Thanks for clarifying your question. The formulation that
you and Dorais give seems perfectly reasonable. You have a
first order language for category theory, where you can
quantify over objects and m …
- 236k
37
votes
Accepted
Is there a computable model of ZFC?
The Tennenbaum phenomenon is amazing, and that is totally correct, but let me give a direct proof using the idea of computable inseparability.
Theorem. There is no computable model of ZFC.
Proof: Su …
- 236k
36
votes
Succinctly naming big numbers: ZFC versus Busy-Beaver
I think your question is not as precise as you portray it.
First, let me point out that you have not actually defined
a function $z$, in the sense of giving a first order
definition of it in set theo …
- 236k
34
votes
5
answers
1k
views
Does the exact pair phenomenon for partial orders occur in your area of mathematics?
Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
Both $b$ …
- 236k
31
votes
Accepted
Intermediate value theorem on computable reals
Let me assume that you are speaking about computable reals and functions in the sense of
computable analysis, which is one of the most successful approaches to the topic. (One must be careful, since t …
- 236k
31
votes
3
answers
3k
views
Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just fro...
Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, s …
- 236k