# Questions tagged [computability]

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

1,355 questions
114 views

### How to prove that if the set and its complement are recursively enumerable, then both are recursive?

How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive? My idea is that we can make the characteristic function of recursively ...
73 views

47 views

### is it possible to have a mapping reduction between 2 NP complete languages?

so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas. but i just can't figure out a ...
24 views

119 views

### Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
66 views

35 views

### Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function: My problem is the way this proof works. The function ...
2k views

### Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
35 views

### Forever running programm computable?

Is a forever running program computable? For example a program which calculates the biggest natural number.
35 views

### Why is this function computable

I'm struggling to understand why this function is computable. This is the requirement: Consider the following program P, written in a pseudo-C language: ...
82 views

### Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
46 views

### Problem with proving the undecidability of REGULAR$_{TM}$

Sipser in his book provided the following proof for undecidability of REGULAR$_{TM}$: S = “On input $<M,w>$, where $M$ is a TM and w is a string: Construct the following TM $M_2$. ...
Any ideas for proving that $L=\{\langle T \rangle : \text{ time complexity of$T$is polynomial}\}$ is not Turing-recognizable?