1
vote
2answers
45 views

Proving a language is not decideable using a reduction from Busy Beaver?

I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural ...
1
vote
1answer
57 views

Turing machine with repeated strings

How would I go about making a Turing machine to accept the following language L? $$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$ I was thinking counting the number of symbols in the input ...
2
votes
2answers
144 views

Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$ I was asked to prove/disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 ...
1
vote
2answers
94 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
0
votes
1answer
79 views

Turing machines and languages — recursive (enumerable) or not

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could ...
2
votes
0answers
115 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 ...
2
votes
1answer
78 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
0
votes
1answer
151 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 ...
0
votes
2answers
142 views

TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5

I am trying to describe a TM that decides the language $A=\{0^{5^n} \mid n\ge0\}$. I know how to do this for $0^{2^n}$, marking off every other 0 in each pass. In my case would it work marking off ...
0
votes
0answers
45 views

Using Rice's Theorem Correctly [duplicate]

I'm currently learning about Rice's Theorem, and I'm having a bit of trouble understanding when I can and cannot use it. It's my understanding that Rice's Theorem can only be applied to something if ...
0
votes
1answer
99 views

Turing machine with possible transitions to the final state [closed]

Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had ...
1
vote
0answers
70 views

Flowcharts vs DFA resp FSM equivalency

First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I ...
1
vote
1answer
131 views

Prove that all non-recursive languages are infinite

I am wondering this statement above [the title] is true or not. Here is what I've already had : non-recursive means undecidable. I've read this Are all infinite languages undecidable? which says: ...
1
vote
0answers
28 views

Show that the language of all total Turing machines is neither r.e. nor co-r.e [duplicate]

I've been thinking about how to show this but I'm stuck. I'm required to prove this: Show that the language $$\mathrm{TOT}= \{\langle M \rangle : M\text{ is a Turing Machine that halts with all ...
2
votes
2answers
237 views

Complements of Linear Bounded Automata?

Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working ...
1
vote
1answer
133 views

Proving that the language of TMs which only moves left is undecideable

I'm trying to prove that the following language is undecidable:$$ \{ \langle M, w \rangle ~|~ M \text{ is a TM where its head moves left a finite number of times on } w \} $$ But I'm having a bit ...
2
votes
1answer
37 views

If the language of a TM is TMs which cannot self recognize, can the original TM?

I've been thinking about this one for a while: Consider the language of TMs which do not recognize themselves: $L_{s}=\{ \langle M\rangle ~|~ M \text{ does not accept } \langle M\rangle \}$. If ...
0
votes
1answer
334 views

Can a Turing Machine decide only non-regular languages?

I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular ...
2
votes
3answers
509 views

Turing machine for $a^i b^j$ with $i \geq j$

I would have a brief question about how to construct a Turing machine that is accepting only this language: $\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$. I can't come up with any mechanism ...
3
votes
1answer
116 views

Abstract machine that can recognize repetition

Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$. For example, if ${x,y,z} \subset ...
0
votes
1answer
669 views

Undecidable among these for turing machine

Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation? It is undecidable, whether an arbitrary ...
1
vote
0answers
79 views

Correct approach to Mapping Reduction from $E_{TM}$

as the title states, I am trying to figure out if my approach to solving mapping reduction from $E_{TM}$ to some other language is correct. As you surely know, $E_{TM} = \left \{ < M> \mid M \ ...
13
votes
4answers
527 views

Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
2
votes
1answer
332 views

Is it possible that the union of two undecidable languages is decidable?

I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$. I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't ...
5
votes
2answers
279 views

Proof-sketch on the language accepted by a Turing machine

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
2
votes
5answers
2k views

Recursive and recursively enumerable language definition for a layman

I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are . Can some one please tell me what they are in simple words? Thanks ...
2
votes
1answer
275 views

Show the Language is Recursive

I have devised the following TM for the language EQUAL. EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular. Using the TM I devised, how can I show ...
4
votes
1answer
716 views

Gödelization in Turing Machine

I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please ...
0
votes
1answer
123 views

Determining the classification of languages

$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$ $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on $w$}\}$ $L = L_0 \cup L_1$ I need to determine where ...
4
votes
1answer
275 views

Time complexity of an enumeration of SUBSET SUM instances

An instance of the SUBSET SUM problem (given $y$ and $A = \{x_1,...,x_n\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma ...
5
votes
3answers
307 views

How to calculate the number of states in designing a Turing machine?

I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example: $\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$ I ...
6
votes
1answer
247 views

Show that the halting problem is decidable for one-pass Turing machines

$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable. I thought of checking the encoding of ...
8
votes
1answer
301 views

Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

I would like to use your help with the following problem: $L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup CoRE$. I know that to prove $L\notin RE$, it is enough to find a ...
3
votes
2answers
222 views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
4
votes
3answers
768 views

Proving that recursively enumerable languages are closed against taking prefixes

Define $\mathrm{Prefix} (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$. I know that recursively enumerable ...
5
votes
3answers
608 views

Please explain this formal definition of computation

I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts:: Let $A$ be a ...
2
votes
6answers
3k views

Are Turing machines more powerful than pushdown automata?

I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
10
votes
2answers
706 views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...