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

learn more… | top users | synonyms

0
votes
0answers
37 views

Prove that it is undecidable whether a Deterministic LBA accepts an infinite number of inputs [on hold]

Deterministic Linear Bounded Automaton (LBA) is a single-tape TM that is not allowed to move its head past the right end of the input (but it can read and write on the portion of the tape that ...
1
vote
2answers
47 views

Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

Let the following datatype be defined: data T = A | B T | C T T That is, B, B T, B (B T), C A A, C (B T) A and so on all are ...
3
votes
1answer
34 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
3
votes
1answer
81 views

Can every program be turned into a quine?

Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't ...
2
votes
2answers
49 views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
1
vote
1answer
22 views

If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$. Is this true? My intuition is false even if we can find some special case to make it true such as ...
1
vote
1answer
22 views

How do you prove that this TM decides a language that is undecidable? [closed]

In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language $$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w ...
-1
votes
2answers
68 views

Mathematical function vs Computer program

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration. Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets. Then relation $R \subseteq A_1\times ...
1
vote
2answers
115 views

If a DFA can be simulated by a real program, can it be simulated by a TM

In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says ...
8
votes
1answer
84 views

Computing the intersection of two NPDA where it is possible

Apropois to Raphael's suggestion on Intersection of two NPDAs: Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
1
vote
1answer
46 views

Is the language of TMs that halt on some string recognizable?

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$ How do I go about showing that this language is ...
5
votes
2answers
393 views

Is it possible for a language and its complement to both be unrecognizable?

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable? If some other language $S$ and its complement $\overline{S}$ are both recognizable, ...
4
votes
2answers
467 views

Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...
3
votes
2answers
189 views

What is a fixed point in the context of Roger's fixed-point theorem?

In the Wikipedia article on Rogers' theorem, it is stated that all total computable functions have a fixed point. The notation is a little hard for me to understand; a symbol is used that is used to ...
1
vote
1answer
46 views

Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension

Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ ...
8
votes
1answer
599 views

What's flawed about the “save-the-input” method of reversible computing?

I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought ...
1
vote
1answer
74 views

Can Turing Machines decide on computability? [closed]

Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?
1
vote
1answer
53 views

Regarding Turing Machine Halting Problem [closed]

All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting ...
2
votes
1answer
42 views

How do you classify properties as Trivial and Non-trivial? [duplicate]

I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone ...
2
votes
0answers
55 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
1
vote
1answer
96 views

If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?
4
votes
2answers
120 views

Is this language depending on P = NP recursive?

Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language $$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$ ...
2
votes
2answers
85 views

Is equivalence of CFGs decidable for finite sets of grammars?

Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and ...
1
vote
2answers
113 views

The minimization operator is an effective operator

Assume $\{f_i^{(n)}\}_{i=0}^\infty$ is a Gödel enumeration of the $\mu$-recursive functions of $n$ arguments, such that the $S^m_n$ theorem and the universal function theorem hold. Denote the set of ...
1
vote
1answer
87 views

Reduction to complement of Accept Problem

I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \}$$ To this Turing ...
2
votes
1answer
135 views

What's a trivial property?

I am working on a homework question, where I have to show a property P is trivial. This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference ...
1
vote
3answers
99 views

Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
2
votes
2answers
335 views

Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...
2
votes
2answers
111 views

Why is the halting problem unsolvable by a turing machine? [duplicate]

So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable. So any human can determine if a problem halts with rigorous inspection, so why can't a ...
1
vote
1answer
75 views

Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

This is a question from an exam I did today: Given $M$, a turing machine, we need to decide the following: 1) $M$ halts on every input 2) The language of $M$ is CFL My question is, can ...
1
vote
1answer
60 views

Is it possible to encode an arbitrary computation as a series of NP complete problem instances? [closed]

For example, can I make a compiler that transforms a C program (Turing complete language) into a bunch of SAT instances. This encoding would be motivated as a way for specifying a problem piecemeal, ...
1
vote
1answer
43 views

Decidability of an regular expression

I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing. Be A = {(R)|R it ...
0
votes
1answer
30 views

$L \in RE/R$ such that $L^R \cup L \in R$

Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$ Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but ...
1
vote
2answers
74 views

Why have additional symbols on a Turing machine?

What is the point of non-binary printed letters on a turing machine? I understand that these need to be omitted to get a computable number, but why are they used in the first place?
4
votes
1answer
62 views

Is it possible to prove EQTM is undecidable by the Rice theorem?

Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice ...
2
votes
3answers
100 views

Is the set of programs that compute some function other than $h$ recursively enumerable?

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable? Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be ...
1
vote
3answers
157 views

Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the ...
0
votes
1answer
18 views

Decidability of fullness of intersection of a CSL with a regular language

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable? $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$ ...
1
vote
1answer
70 views

Understanding a proof for the existance of a non-computable function

For school, we have a proof that some functions are not Turing computable. The example is: $$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ ...
1
vote
1answer
135 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
0
votes
1answer
125 views

Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
1
vote
3answers
133 views

Is the image of a total, non-decreasing function decidable?

This is an exercise I've been struggling with for a while: Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of ...
7
votes
1answer
500 views

Is any language that can express its own compiler Turing-complete?

A comment over on tex.SE made me wonder. The statement is essentially: If I can write a compiler for language X in language X, then X is Turing-complete. In computability and formal languages ...
0
votes
1answer
88 views

Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be: decidable (recursive) or undecidable (nonrecursively enumerable) ...
-1
votes
2answers
87 views

Can $\emptyset$ be reducible to any other language? [duplicate]

While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to any other language, i.e., $\emptyset \leq A$ such that $A$ is a language over ...
5
votes
2answers
93 views

What is the field studying the search and generation of computer programs?

This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
1
vote
1answer
84 views

Trying to break the proof of undecidability of the halting problem

Posted this question on cstheory.SE where they said to go here: I read the demonstration of the Halting problem, it is done by reductio ad absurdum where the push to get to the absurd is to use ...
4
votes
2answers
212 views

What can Idris not do by giving up Turing completeness?

I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific ...
1
vote
2answers
37 views

How to mark things in the input? [duplicate]

Sipser theorem 4.4* $E_{DFA} = \{ \langle A \rangle \mid \text{A is a DFA and } L(A)=\emptyset\}$ is decidable. I could not quite understand the solution, I'll quote it: On input ...
0
votes
1answer
33 views

Turing Machine 'marking' specific portion of encoding

Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states? For example, ...