# Questions tagged [computability]

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

1,355 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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$ ...
79 views

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 ...
61 views

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 ...
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 ...
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, ...
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(...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$?
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 ...
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$...
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 ...
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. ...
25 views

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 ...
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?
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. ...
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$ ...
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 ...
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 ...
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 ...