# Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

1,677 questions
Filter by
Sorted by
Tagged with
19 views

### DNF and CNF and Complexity Theory

$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$. If that case is true and the conditions ...
6 views

### In the PCP, can we remove all dominos with the same top and bottom strings and still get a match?

Suppose we have an instance P of the PCP, and there exists a match for it. I am wondering if we remove all dominos that has the same string on the top and bottom, would there still be a match? My ...
105 views

### What does an admissible numbering of computable functions look like?

I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions. Initially my take on such an enumeration was from the point of view of an ...
26 views

### Relative primality is primitive recursive

How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?
13 views

### AMBIG_NFA decidability problem

As suggested by the title, $AMBIG_{NFA}$ consists of descriptions of all NFAs that accept some string along two computation branches. The original question is to show that it's decidable. Although I'm ...
51 views

36 views

### Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
100 views

### Is the halting problem pointless?

Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot ...
97 views

### Prove for Rice’s Theorem(Is the reduction used ? )

I was reading formal proof of Rice theorem in wikipedia: https://en.wikipedia.org/wiki/Rice%27s_theorem#Formal_proof I want to know is what we used here is the reduction algorithm : we reduce the Halt ...
88 views

59 views

### Why, intuitively, does the Ackermann function require $\mu$-minimisation?

I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive ...