Questions tagged [computability]

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

1,354 questions
0answers
74 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
2answers
66 views

Is this system Turing complete?

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries. I came up with the ...
1answer
51 views

Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
0answers
23 views

All the ways in which Turing machines are used

The Turing machine model can be used to do computation in several ways. Two ways I know are: For a Turing Machine that checks whether a particular string is present in a language or not, when the ...
1answer
52 views

What is the definition of computable partial function?

Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input ...
0answers
31 views

Which subsets of the set of all recursively enumerable languages is recursively enumerable?

I know that, Rice's say's any non trivial subset of the set of all recursively enumerable languages is not recursive. I also remember reading some characterisation of the recursively enumerable ...
1answer
646 views

Does a notion of a context-free complete language exist?

Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
1answer
16 views

2answers
44 views

How can MLTT etc encode computability?

I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For ...
1answer
36 views

decision diagram and decision tree difference

What are the difference between decision diagram and decision tree? Is BDD a type of DD? what are the other type of DD? what are the algorithms used for it
3answers
48 views

Given an CFG determine if $\varepsilon \in L(G)$

Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ? The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1answer
53 views

1answer
45 views

If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$

Let be $A, B \subset \mathbb{N}$ are recursively enumerable, $A\cup B$ and $A \cap B$ recursive. I want to show that $A$ and $B$ are recursive. By negation theorem $X \subset \mathbb{N}$ is ...
1answer
58 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
1answer
34 views

If a language is contained in other langauge, is it of the same complexity?

If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P? Thanks :)
2answers
58 views

1answer
52 views

Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

I thought about these languages: $$L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$$ L_{2} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid ...
3answers
136 views

Proof that total computable functions are not enumerable

In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made: Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all ...
2answers
112 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 ...