Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

2
votes
1answer
25 views

Robustness of non-context-free proof against trivial manipulation

First, we state here a theorem that is well-known in computability theory: $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$ And, the standard proof is using pumping lemma. At ...
2
votes
1answer
40 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
2answers
38 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 ...
1
vote
1answer
20 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
2
votes
3answers
41 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. (...
0
votes
1answer
35 views

Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable

Consider the following language $$EQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\}$$ Given the fact that $EQ_{DFA}$ is decidable, how can I prove that the language $$...
1
vote
1answer
69 views

Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
1
vote
1answer
46 views

Are the definitions of recursively enumerate equivalent?

There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that $$A:=\{n \in \...
3
votes
1answer
38 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 ...
0
votes
1answer
52 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 ...
1
vote
0answers
31 views

One-tape one-non-blank-symbol Turing machine

Consider the following Turing machine model: Each TM has $1$ tape infinite to the right, with left-marker $\$$ as usual Each TM has one blank symbol $\mathrm{\underline{b}}$ Each TM has ...
1
vote
1answer
32 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 :)
1
vote
2answers
47 views

How to define (logically) the complement language?

I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language: $$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{...
-3
votes
1answer
57 views

Is it there any computer/cellular automaton/brain to compute logically impossible and incomputable things? [on hold]

Is it there any computer or cellular automaton or model of the brain where they could compute logically impossible things and incomputable things? For example, if we wanted to compute/simulate/think ...
1
vote
3answers
52 views

Does intersecting the output of 2 programs give the output of another program?

Let $S$ be the set of all programs that take integers as input and return integers as output and halt on all inputs. Does there exist a pair of program in $S$, call them $P_1$ and $P_2$, such that ...
1
vote
1answer
20 views

does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false....
3
votes
1answer
89 views

Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?

Let $$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$ Is $L_{300}$ decidable? My intuition is it is decidable because given $M$ and $w$, we need ...
0
votes
1answer
20 views

Basic control statements for Turing equivalence? [duplicate]

Apologies ahead of time, I don't fully understand what I'm asking... But, is it possible to program using only 'while loops' and still be Turing equivalent? Or more generally, can I do everything ...
1
vote
1answer
60 views

Decidability of language L = { n : ∃x∈N, n = 3x+2 }

I've recently came across this language and I don't know if my hint for proving its class is correct or not. $$L = \{ n : \exists x \in N, \,n=3x+2 \} $$$n$ is in binary format. I think $L$ is ...
0
votes
1answer
41 views

Class of given language

The language given is: $$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$ I have to find the class to which this language belongs. Now according to my intuition, ...
3
votes
1answer
37 views

Why does existence of predecessor imply adequacy of a numeral system?

I encountered this result when working with $\lambda$-calculus (so every element I mention here was a $\lambda$-expression there [1]), but I will express everything with, more understandable to ...
0
votes
1answer
36 views

Is the language of Turing machines that calculate a given function $f$ in RE or coRE?

For a function $f$, consider the language $$L=\{\langle M\rangle\mid M\text{ computes }f\}\,.$$ Where does the language above is and how do I prove it? To me it seems that it's not in RE nor coRE but ...
0
votes
1answer
42 views

sha256 computability class

Is it correct to say that since the SHA256 function domain is finite (as reported here) we can build a DFA that calculates this function (i.e. trivially a giant lookup table)? Furthermore, if we ...
0
votes
1answer
24 views

Priority of symbols in a notation for projections

We define an initial function called projection as $$I^k_i(n_1,\ldots,n_k) = n_i, \quad i \leq 1 \leq k, \quad k \in \mathbb{N}.$$ Suppose now that we want to define it in some programming language ...
-1
votes
1answer
60 views

Solving problems that DTM can't solve

Let L be a problem that DTM can't solve. Can we prove that there is an abstract machine that can solve this problem? Here, L is not Halting problem or Hilbert's tenth problem (because we proved that ...
1
vote
1answer
25 views

Proof that a quantum computer is equivalent to some logical circuit

My question is about the quantum computer. I have tried to prove that the quantum computer is equivalent to some logical circuit. I know this has already been proven, but I will present my attempt: ...
0
votes
0answers
25 views

Is there a mapping reduction of E(tm) to OVERLAP(tm)?

$E_{TM}=$ { < $M$> $|$ $M$ is a TM; $L(M)$=$\varnothing$} Where $L(M)$ is the language accepted(recognized) by $M$. $OVERLAP_{TM}=$ {< $M_{1}$,$M_{2}$> $|$ $M_{1}$,$M_{2}$ are TMs; $L(M_{1})\...
3
votes
2answers
74 views

Proof that Turing machines and computers have same power

How do we prove that any logical circuit can be simulated by a Turing machine? For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, ...
1
vote
1answer
34 views

M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time

$M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape. let $c_{1}, c_{2}$ be two configurations of $M$. A configuration is defined like this: $uqv$ where $(q\in Q; u,v\...
1
vote
0answers
25 views

Is this solution is bad for the coin change problem? [closed]

was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious. removing the ...
-3
votes
1answer
206 views

Is Alan Turing's proof of the incomputability of halting problem invalid?

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...
3
votes
1answer
40 views

Are all terms of type forall a. a operationally bottom?

Is there a proof that all terms of type $\forall{a}. a$ are operationally $\bot$, in a non-weakly-normalising version of System F? If you ask a free theorem calculator such as this one for the free ...
0
votes
2answers
120 views

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing ...
3
votes
1answer
25 views

If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?

If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$? I think that as we know nothin about $M$, in general case we can't determine wherther a random ...
1
vote
1answer
38 views

Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

I'm stuck on this problem: Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$...
1
vote
1answer
31 views

What's wrong with the following argument that $NP \subset coNP$? [duplicate]

What's wrong with the following argument that $NP \subset coNP$? let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$. ...
1
vote
1answer
68 views

Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable

So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way: let's suppose that $g$ is the computable function that represents $D$ $$g(x) ...
1
vote
1answer
43 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 ...
0
votes
3answers
57 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 ...
1
vote
2answers
41 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 ...
2
votes
1answer
69 views

Decidability of a set containing first symbols of elements of a decidable set

Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$ Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure $x_i := \alpha_i \beta_i$, where $\...
3
votes
1answer
287 views

How is deciding a problem not equivalent to finding a valid certificate for verification?

Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$. Since $Q$ is in $NP$, there exists a verification ...
0
votes
1answer
50 views

Turing machines and their computational power

Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the ...
0
votes
1answer
59 views

Are there any implementations of computability logic?

I'm currently looking into Japridze's computability logic. It looks great, but I was wondering whether any programming languages or systems implement it. Does anyone know of any implementation? ...
6
votes
2answers
1k views

Why does the copycat strategy work for two parallel chess games?

I'm currently looking into computability logic. Japaridze explain that a game !P v P like !Chess v Chess is always winnable thanks to the copycat strategy (http://www.csc.villanova.edu/~japaridz/CL/3....
2
votes
1answer
125 views

Decidability of L

I have the following problem. If L is decidable and L = L1 u L2 (union). So are L1 and L2 decidable, too? I know that, if L is decidable, the complement is also. And this means the complement is ...
3
votes
1answer
46 views

Connecting strings in a graph is a PSPACE problem

We define the following problem as: Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$. We define, for every natural number $n$ the graph $G_{M,n}$ by: $V_{M,n} = \{a,b\}^n$,...
0
votes
1answer
41 views

Obtaining a computational history of a Turing Machine

I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In ...
2
votes
1answer
60 views

What is the current state of the art in solving the halting problem? [closed]

Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them. To be a little more ...
1
vote
1answer
27 views

Give a Search Problem in co-NP

Ex.1. Give a Search Problem whose deciding Problem is in co-NP. Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right? Then would asking ...