# Questions tagged [computability]

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

2,432 questions
Filter by
Sorted by
Tagged with
42 views

### On existence / computability of mathematical objects like √2 [closed]

numbers like √2 or 1/9 are mathematical objects but they are abstract concepts (because we could not calculate them). It is not a natural nubmer but rather an infinite sequence of fraction digits. ...
• 95
90 views

### $\omega$-consistency in Goedel's completeness

To prove $PA\not\vdash \lnot \Delta$, where $\Delta$ is the Goedel's sentence, satisfying: $$PA\vdash \Delta\leftrightarrow \lnot Prv(\overline{\Delta})$$ Why cannot we say: If $PA\vdash \lnot \Delta$,...
• 4,223
64 views

62 views

### Algorithm for Determining Truth of First-Order Sentences in Complex Numbers

Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
• 87
90 views

### Decidability in Natural Numbers with a Combined Function [closed]

It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
• 87
1 vote
23 views

### Relationship between relative PA degree and Turing reducibility.

According to Reverse Mathematics, Definition 2.8.24 by Dzhafarov–Mummert, we say that a function $f \in 2^\omega$ has PA degree relative to $g \in 2^\omega$ if the collection of $f$-computable ...
• 104
1 vote
63 views

105 views

### Why doesn't this diagonal argument work?

I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the ...
1 vote
76 views

### What is the largest known "computational" ordinal

I am interested in the computational implementation of ordinals. What I mean by that, is a data structure T and a function/algorithm "compare" that takes two arguments of type "T" ...
• 11
54 views

Apologies if I'm asking a naïve question as I've only recently learned about the concept. What would be the practical implications (if any) of having access to a magical black box providing the ...
• 1,472
58 views

1 vote
34 views

### Wainer hierarchy, ordinal free definition below $f_{\epsilon_0}$

Is it possible to define Wainer hierarchy below $f_{\epsilon_0}$ in a way that would not refer to ordinals at all?
• 173
1 vote
81 views

### A question on a generalization of recursively inseparable sets

$\mathbb{N}$ denotes the set of natural numbers $0,1,2,\ldots$ In what follows all sets are subsets of $\mathbb{N}$. The classical definition that two sets $S_1$ and $S_2$ are recursively inseparable (...
• 11
160 views

### What's the difference between coding in second-order arithmetic and first-order arithmetic?

I am trying to understand the difference in developing coding in first-order arithmetic and second-order arithmetic. I have read various kinds of phrases like "coding can be done in $I\Sigma_0$&...
143 views

• 367
29 views

### Transition in lemma proof in maximum set proof

(Sorry if it doesn't render MathJax right, I haven't figured out how it works here) I've been reading a lot of proofs of existence of maximal set and here is the problem. I'm working with proofs that ...
1 vote
78 views

### Since corollaries of ZFC are r.e.，why there are Turing degrees that are not r.e.?

for any Turing degree a and A∈a，and a fixed x,we can just put the formula “x∈A” into the Turing machine which examines whether a formula is a corollary of ZFC.It halts iff ZFC proves “x∈A”.So we got ...
• 11
76 views

### Are the models of PA recursively enumerable?

Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
1 vote
38 views

### Coding for Kleene's closure of any countable alphabet (with textbook reference)

If $S$ is a countable alphabet, I suppose there exists an explicit and effective (i.e. computable) injection from $S^*$ to the set $\mathbb{N}$ of natural numbers. Could you provide a textbook showing ...
47 views

### textbook proving a theorem of computability theory (r.e. sets)

This is a well-known result of computability theory "A recursively enumerable union of recursively enumerable sets is still recursively enumerable" Could you point me to a textbook where ...
57 views

### Factorial for Natural Number Object

It is Awodey Exercise 17 in Chapter 9. It asks to define factorial as an arrow $N \to N$ for a natural number object. Awodey page 246 and 247 defines how to add a natural number by recursion. That is, ...
• 4,223
1 vote
63 views

• 735
1 vote