# Questions tagged [computability]

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

1,355 questions
708 views

### Is L={<M>|M is a TM and L(M) is uncountable} decidable?

Is $L=\{\langle M\rangle\mid \text{$M$is a Turing machine and$L(M)$is uncountable}\}$ decidable? My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is ...
50 views

### Do NFAs with $\varepsilon$-moves never terminate?

Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser, Without reading any input, the machine splits into multiple copies one following each of the ...
42 views

### How can I build a fool proof security system? [closed]

From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not. That tasks looks very similar to me than deciding ...
69 views

### Halting problem for polynomial space bounded Turing machines

A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable. I do not ...
50 views

### Show that the following language is not recursive:

$L = \{w \mid M_w \text{exists and it accepts a word } x_1 = 0x \text{ if and only if it accepts } x_2 = 1x\}$ ($x \in \Sigma^*$, so $x_1$ is starting with a 0 and $x_2$ is obtained from $x_1$ by ...
216 views

### Reduce undecidable language to decidable language?

What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable): If $M$ accepts ...
42 views

### function application of N x N -> N

Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following ...
39 views

### computably defined function with non computable range

Are there examples of functions that can be defined computably, though the existence of their range is not computable?
96 views

### Is there a language that can be Turing-reduced from all languages?

I don't think so, because $A_{TM} = \{<M,w>\mid \text{M accepts w}\}$ is not Turing-decidable. Is this the right way to think about?
121 views

### Is the language of all deciders recognizing empty language decidable?

I TA for a course in theory of computation and this came up as an interesting question. $E_{TM}$ is the set of TM descriptions where the machine's language is empty. Of course, $E_{TM}$ is ...
62 views

### Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
7k views

### Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...
42 views

### Is there a name for the class of functions whose totality can be proved using “Ackermann-like” reasoning?

Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
68 views

39 views

### Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
156 views

### prove A is co-re

Working on some cs theory and solving a problem on computationally [=recursively] enumerable languages: A language $A\subseteq \{0,1\}^*$ is co-c.e. if and only if there is a decidable language ...
26 views

### how to mapping reduce any r.e. language to the diagonal language K?

We know that the halting problem $A_{TM}$= $\{(e,x) \mid M_e(x)$ accepts$\}$ and the diagonal language K= $\{e \mid M_e(e)$ accepts$\}$ are mapping reducible to each other. Recall that A mapping ...
68 views

### how to mapping reduce any r.e. language to the diagonal language K?

We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation. I would like to ...
79 views

### show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
92 views

### 3-Col using each colour exactly $|V|/3$ times

Is the following problem in P? Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times? I believe it is as we are trying to sample three sets (one for each colour) of ...
28 views

145 views

54 views

### prove every language got a language that is harder

I am prety stuck over here: prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$ $L''\ngeq L'$ basically it means L' is the hardest... my intuition tells ...
327 views

### Prove by reduction EVEN TM is undecidable

...
Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable? I know the union need not be recursive, because deciding if ...
### Example of non extensible functions ( $f(x) \notin EXT$) for reduction
This is the definition of $EXT = \{x\ | \varphi_x\ can\ be\ extended\ to\ a\ total\ computable\ function \}$. I'm trying to proof that $\overline{K} \le_{rec} EXP$ and I can't think of an example of a ...