# Tagged Questions

Questions about problems which cannot be solved by any Turing machine.

65 views

### Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from ...
61 views

### TM that accepts all strings is recognizable or not?

Lets say we have the following language $L = \{\text{$M$is a TM such that$M$accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct ...
57 views

### How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}. How can I prove that this is undecidable? I have considered trying to build the ATM ...
34 views

### Example of a simple recognizable language, whose complement is not recognizable

Can any one provide me with a simple language that is recognizable, but that it's complement is not? I have read that recognizable languages may have this property but I am yet to find an example to ...
51 views

### Is converting an ambiguous grammar to an unambiguous grammar computable?

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
49 views

### Problem complete for the class of ALL languages

$\text{ALL}$ is literally the class of ALL languages. Are there $\text{ALL}$—complete problems? That is, are there problems for which a solution would allow one to solve any problem whatsoever? ...
26 views

### How to show if the following function isn't computable?

Given a $\Gamma = \{0,1, \square\}$ and an function $f(n)$ which calculates the maximum number of steps from a turing-machine, with $n$ states and which holds on an empty tape. How to show that the ...
42 views

### Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of ...
70 views

118 views

87 views

### two languages reducible to each other can belong to RE and recursive?

If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false? A L1 is decidable and L2 is undecidable. B L1 is recursive and l2 is RE C ...
16 views

### Computing shifted fix point in the BSS model

Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is ...
48 views

### Undecidable language and Turing Machines

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ...
### Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?
I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input. Here's the copy-paste of that ...