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