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 tagged [computability]

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

2
votes
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 ...
2
votes
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 ...
0
votes
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'$...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
3
votes
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)?
1
vote
1answer
16 views

How hard can identifying non-membership in a semi-decidable language be?

A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\...
1
vote
2answers
59 views

Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility?

There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a ...
1
vote
1answer
54 views

Proof that the Blank Tape Halting Problem is undecideable [duplicate]

I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not) Proof: Suppose that the Blank Tape ...
0
votes
0answers
19 views

example of $A \leq_m B$ where $A$ is decidable but $B$ is undecidable [duplicate]

I know that given a mapping reducibility function $\leq_M$ from $A$ to $B$, if $A$ is undecidable, then $B$ is also undecidable. But if ever $A$ is decidable, from what I think, it does not ...
0
votes
1answer
29 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
52 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
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 ...
1
vote
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
2
votes
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. (...
0
votes
1answer
53 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
105 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
50 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 \...
4
votes
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 ...
0
votes
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 ...
1
vote
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 :)
1
vote
2answers
58 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
68 views

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

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
23 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
96 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
26 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 ...
-1
votes
1answer
50 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
41 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
38 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
28 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
61 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
26 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
31 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
140 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
35 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
27 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
278 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
42 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 ...
1
vote
2answers
148 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
28 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
41 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
33 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
81 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
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 ...
0
votes
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 ...
1
vote
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 ...