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

3
votes
1answer
36 views

Implementation/translation of the $s^1_1$

This is the Lisp code (from wikipedia) that implements the $s^1_1$ form of the $s^m_n$ theorem ...
1
vote
2answers
279 views

Is the class of Turing-recognizable languages closed under Homomorphism?

Would this proof work? Given a language $L$ that is Turing recognizable and a TM M that recognizes it and a homomorphism $f$, we build a NTM M' that recognizes $f(L)$, M' looks like this: On input ...
3
votes
2answers
260 views

Is there any data structure that can't be represented or described inside a computer?

We all know that, at least theoretically, there are several possible models of computation, varying in structure. Strictly speaking, there are several (not just one) models of computation that exist ...
1
vote
1answer
469 views

Closure of Turing-recognizable languages under homomorphism

I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism. But what's really the difference? Doesn't closure under ...
3
votes
2answers
1k views

Why is “accepted by Turing Machine with even number of states” a trivial property?

$$ L = \left\{ \left< M \right>~\middle|~ \small{ \begin{array}{l} L(M)\text{ is recognized by a Turing Machine} \\ \text{having even number of states} \end{array} } \right\}. $$ Isn't $L$ same ...
1
vote
0answers
43 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
1
vote
2answers
114 views

Detect whether one Turing machine invokes another

Given two Turing machines $M,M'$, is it possible to check whether $M$ invokes $M'$? In other words, is the following problem computable/decidable? Inputs: Turing machines $M,M'$ Question: Does $M$ ...
0
votes
1answer
79 views

If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

So this is how i solve it but someone told me its wrong: $B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\...
0
votes
0answers
90 views

Why is set of Turing machine set DD = {⟨M⟩ | ⟨M⟩⟨M⟩ not in L(M)} not decidable?

To prove that the set $\mathrm{DIAG} = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\}$ is not decidable, we can assume, to the contrary, that there is a Turing Machine $M$ such that $L(M) = \...
3
votes
0answers
35 views

From SETH to circuit lowerbounds

Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR) In threshold ...
0
votes
1answer
61 views

Does the language of TM's that repeat a configuration infinite times semi-decidable or not?

Let us define the following languages: $$ {L_1 = \{\langle M\rangle : M \ \text{is a TM and $\exists w\in \Sigma^*$ s.t $M(w)$ repeats a configuration infinite times}\}} $$ $$ L_2 = \{\langle M\...
2
votes
1answer
187 views

Solving diophantine equations — does having a bound on the size of the solution help?

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$: H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ ...
1
vote
3answers
37 views

How do I check if two if-stmt blocks are the same?

Consider the following two snipets of code: If a >= 5: If b == 0: .... Else: .... Else if a <= 5: .... ...
0
votes
1answer
40 views

prove that $h(x)$ is partial recursive

If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive $$ h(x) = \begin{cases} \...
7
votes
2answers
106 views

Ackerman hierarchy for higher order primitive recursion in System T

Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he ...
0
votes
0answers
151 views

Decidability of intersection of two languages of same type

Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable? I have the same question for the case when $L_1$ and $L_2$ belongs to ...
0
votes
0answers
19 views

Does there exist a conservative algorithm to determine if a certain property is satisfied at a certain part of a program?

... x = a / b; For the above code, for example, is there a way to determine whether b could be zero at the time of division, ...
1
vote
1answer
109 views

L(G) = ∅ is undecidable?

For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable? I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(...
1
vote
4answers
961 views

Whether TM accepts epsilon?

L = {< M > $\mid$ L(M) is $\epsilon$ } Why is the above problem undecidable and not decidable? Can't we just check whether initial state is itself final state and say TM accepts epsilon if initial ...
0
votes
0answers
19 views

Give an example of a language where both L and ¬L is not semidecidable? [duplicate]

I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
0
votes
0answers
37 views

Can machines of finite size ever solve their own halting problems?

A real-life computer can only store programs and inputs up to a certain length, which means that its halting problem can be solved with a lookup table. The most obvious way to represent this table ...
1
vote
0answers
116 views

Difficulty in reducing non halting problem to a given problem

I am having difficulty in reducing non halting problem to the given problem to prove that language is non R.E For eg Completeness problem of TM . In the above problem, we accept $\Sigma^*$ if H ...
1
vote
0answers
123 views

Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
1
vote
1answer
54 views

R.E or non R.E?

$L_1= \{ \langle M \rangle \mid L(M) \text{ is strings of length between } 1 \text{ and } 5 \}$. $L_2 = \{ \langle M \rangle \mid L(M) \text{ is strings of length at most } 5\}$. I am able to ...
-2
votes
1answer
361 views

complement of a NON RECURSIVELY ENUMERABLE LANGUAGE

Define languages L0 and L1 as follows : L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halt on w} Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second ...
0
votes
2answers
238 views

What does “effective enumeration” in Turing machines mean?

what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER? so effective enumeration is possible ...
0
votes
2answers
72 views

Classification of the complement of a language

$L = \{ \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$. What is complement of this language? my attempt: the complement is: $M$ accepts no two strings of same ...
1
vote
1answer
94 views

Generating a Context Free Grammar(CFG) from a Language

I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I ...
0
votes
0answers
74 views

prove that the language LRE is decidable

given the language LRE= { 〈M〉 | L(M) ∈ RE } prove that the language can be found in R( which means it's decidable). if i use reduction, how can i use for example ADFA language to solve it? and is ...
25
votes
7answers
6k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
1
vote
1answer
72 views

Proving that a class of languages is a subset of RE for Rice Theorem

Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$ where $<M>$ is a valid encoding of a turing machine. I know that the language is applicable for Rice Theorem. Now, I ...
4
votes
2answers
626 views

Is it possible to prove Turing irreducibility

Given two languages $L_1$ and $L_2$, is there a known way to show that $L_1\not\leq_T L_2$? In other words, is it possible proving that there is no Turing reduction from $L_1$ to $L_2$?
17
votes
2answers
2k views

Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

Is a Turing machine without the ability to write on blank cells less powerful than standard Turing? I think the answer is yes but i'm unable to find a computation that standard Turing machine can do ...
1
vote
0answers
190 views

Converting a non-deterministic context free grammar to deterministic

I have the non-deterministic context free grammar $$I \to abcX | abdY$$ $$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...
2
votes
0answers
43 views

How do I develop a structured work method for theoretical computer science? [closed]

Please excuse the soft question and please dont close it prematurely as too broad. When working on assignments that includes a wide range of topics from theoretical computer science (see tags), I ...
2
votes
1answer
50 views

Proving or disproving a set of total functions is countable

Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. ...
1
vote
1answer
25 views

Integer Programming Complexity

I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$ and $D$, find all sequences $0 \lt a_1 \lt a_2 \lt \dots \lt a_n$ are there such that: each $...
28
votes
2answers
4k views

Church-Turing Thesis and computational power of neural networks

The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine. The paper "Analog computation via neural networks" (Siegelmannn and Sontag, ...
3
votes
0answers
57 views

Is the number of tests needed to know if a program computes the identity computable?

Given a $\lambda$-term $t\in \Lambda$ and an integer $k$, we say that $t$ behave likes the identity when applied to $k$ if $tk\to_\beta^*k$ (where the integer is represented as a church numeral). We ...
0
votes
1answer
37 views

Proof of equivalence of L0 and language accepted by made up machine [duplicate]

I have a made up machine, which has the same definition as Turing machine, but the transition function and the step of computation of the machine. What would be the approach of the proof that the ...
1
vote
2answers
1k views

Decidability of whether a language described by Turing machine is regular

I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, ...
0
votes
0answers
98 views

Is {< M >| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD?

Are these languages in D, SD/D, or not in SD? $$L_1 = \{\langle M \rangle\mid L(M)\cap (ab)^*\text{ is infinite}\}$$ I kind of understand decidability and undecidability problems, but the "$\cap(ab)^...
3
votes
1answer
64 views

Computability of an expression of a function rather than a function itself?

Let's assume we're talking about real functions purely for clarity purposes, but my question is more general. We say that a function $f$ is computable, if for a given $x$, a turing machine can output ...
1
vote
0answers
37 views

Difference between Non R.E and Co-R.E [closed]

Can someone please tell me the difference between Non re and CoRE languages with an example?
-1
votes
1answer
542 views

How would one reduce HaltTM to ATM

Assuming that ATM is decidable, how to build a TM S that uses a TM R that takes as input and decides if M accepts w, to decide HaltTM, which we already know is undecidable, hence ATM isn't decidable. ...
0
votes
1answer
94 views

Decidability of whether CFL = RL

Let L1 be a language generated by a CFG. Let L2 be a language generated by a regular grammar. Is L1 = L2 ? Is the above problem decidable or undecidable ? If L1 = L2 then L1 $\cap$ L2' = $\phi$ ...
9
votes
4answers
3k views

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak): A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not ...
0
votes
2answers
368 views

Infinite union of regular language

Deciding if the infinite union of a set of regular languages is regular is undecidable. By closure property of regular languages, regular language is not closed under infinite union so is the above ...
1
vote
0answers
89 views

Is it decidable whether the language of a given CFG contains a palindrome? [duplicate]

Given a context-free grammar G. Is it decidable, if the language $L(G)$, which is generated by G, contains a palindrome? My suggestion is, that it is undecidable, but I do not have an idea for a ...
1
vote
2answers
62 views

Can two deterministic turing-machines avoid each other in a sidewalk? [closed]

Imagine a turn-based game where two robots are placed on opposite sides of a 16x16 board, facing each-other. Each robot, at each turn, can perform one of 2 moves: move (moves forward), turn (turns 90 ...