# 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).

1,639 questions
20 views

### What are the conclusions we can draw from Kleene's Recursion Theorem regarding computability?

Kleene's Recursion Theorem in his Introduction to Metamathematics $\S66$ is written Theorem XXVI: For any $n\geq0$, let $\textbf{F}(\zeta;x_1,...,x_n)$ be a partial recursive functional, in which ...
21 views

### Is every not recursively enumerable set also productive?

I understand that every productive set is not recursively enumerable, but is the other way around also true? If not, what is an example of a set which is not r.e. but not productive? Update: The ...
23 views

35 views

### Confused about non-computable real numbers and countability. Is Cantor diagonalization a computation?

Suppose I start with the set of computable real numbers between 0 and 1. Now these are countable. So I follow Cantor's diagonalization argument to construct a real number B between 0 and 1 outside ...
39 views

### Proving undecidability of group isomorphism problem from an unsolvable word problem

From The Princeton Companion to Mathematics, IV Branches of Mathematics, pages 126-127: Suppose that $\Gamma = \langle A | R \rangle$ is a finitely presented group with an unsolvable word problem, ...
233 views

### Why does this procedure terminate? Or are there any numbers for which it doesn't?

I don't really have good formal education in theoretical mathematics, so please don't be upset if this is obvious question, but on the other hand I don't believe I am the first one to think of such ...
39 views

### If a length is 1 and then it's elevated to two then what is it? [closed]

If $x=1$, then that means that $x^2 = 1$, also. Is the case the same if it has to do with lengths? That's if I got the $|x| = 1$ and then I raised to the power of two so $|x|^2= ...$ will it then be 2 ...
33 views

50 views

### Diagonalization/fixed point lemma in logic vs computability theory

The fixed point/recursion theorem in computability theory and the diagonalization lemma in logic are really similar and the standard proofs of these theorems can be mapped in a one-to-one way (I tried ...
32 views

### Application of Generalized Rice's Theorem

I'm trying to understand how to apply the generalized Rice's theorem to prove that a problem is Turing-Recognizable. Suppose that I have two TMs and I have to evaluate if there exists a string that ...
13 views

### Question about Proof: Semi-decidable => Recursively Enumerable

Def. A set A is recursively enumerable if $A = \emptyset$ or if there exists a total computable function $g$ such that $A = R(g)= \{z | \exists x. g(x) = z \}$. Def. A set A is semi-decidable if ...
29 views

### Compute a series from a sequence

Let's say I have a sequence $s_n$ of numbers, and I want a series $a_i$ which computes the sequence; that is $\sum_{i=0}^\infty a_i n^i = s_n$ Clearly $a_0 = s_0$, but after that I am stuck. I need ...
37 views

### Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
29 views

### is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
235 views

### Does “every” first-order theory have a finitely axiomatizable conservative extension?

I've now asked this question on mathoverflow here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ ...
36 views

### Is every degree above ${\bf 0''}$ PA over something close to itself?

The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not ...
78 views

### What does this notation mean? $\Phi(x) \downarrow, \Phi(x) \uparrow$

I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am ...
43 views

### What is a “n-valued function”?

Has $n$ parameters? i.e. 0-valued function: $f(\emptyset)=2$ 1-valued function: $f(x)=x$ 2-valued function: $f(x,y)=x+y$ 3-valued function: $f(x,y,z)=x+y+z$ Not sure