Tagged Questions

26 views

Turing Machine for $L$={$a^nb^m: m=n^2, n \geq 1$}

The problem only requires a description of the machine. I was thinking for each a you need to find 1 + 2k b's where k is the a your on. (ie for the for the first a find 1 bs, the second find 3 bs, ...
33 views

Multi-Tape Turing Machines to find palindrome

Given an Alphabet {a,b,c} , produce a Turing Machine which recognize if a given input string X is a palindrome. means if X is a palindrome, TM is halting and accepting, else halting and rejecting. ...
28 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
54 views

Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Was stuck on this for a bit so I need to know if I am on the right track. To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable ...
73 views

Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

$\textbf{Problem}:$ $L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$. $B_{TM}$ = $\{ \langle M \rangle$ | ...
68 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
115 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
86 views

If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

Question: Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are). Definition of a decidable ...
163 views

prove Turing recognizable

This is actually an old exam question its not my homework; Let L = { : M is a TM with an input alphabet of {a,b} and M accepts at most one word, i.e. M either accepts no words or accepts exactly one ...
64 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
11 views

Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$. Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$ Is A semi-decidable (Turing recognizable or recursively ...
31 views

Constant value function Turing machine.

How would one go about writing a Turing machine which always computes to a certain value? If the value is small, the problem is trivial of course, but how could I write a Turing machine for the ...
45 views

Turing machines and tape complexity

Are the following statements true and/or false? There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have: (*) ...
77 views

Recursively enumerable language of Turing machines

If you have the language $L_{h}=\{M_{i} | (\exists z \in \sum ^{*}) M_{i}\text{ halts on some input } z\}$ where $M_{i}$ are Turing machines, is $L_{h}$ recursively enumerable? I'm fairly certain ...
78 views

Variation of 3SAT is in NP-Complete

Consider the problem of "K-3SAT", a variation of 3SAT: Given a 3CNF formula O and an integer k, the machine determines whether the formula O has a satisfying assignment in which at most k variables ...
46 views

Proving that the independent set problem is in NP-Complete

Consider the problem of "Independent set" in grahps. Given a graph G and an integer k, the machine determines whether the graph G contains an independent set of size k. I need to prove that it's in ...
95 views

Describing a multitape Turing Machine that enumerates the set of $i$ such that $w_i$ is accepted by $M_i$

I am having trouble with this problem. It regards the theory of Turing Machines. Describe a multitape Turing Machine that enumerates the set of $i$ such that the word $w_i$ is accepted by the ...
90 views

Showing this language is not decidable by rice theorem or reduction

Consider this language: L = {<M1,M2> : M1 and M2 are TMs and L(M1) contained in L(M2) contained in {1}*} Intuition says that it's undecidable, though can ...
318 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$is a Turing machine and$L(M)$is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
46 views

Prove or disprove: Superlanguages of Turing-recognizable languages are themselves Turing-recognizable.

Consider the following claim: Prove or disprove: If $L_a$ is Turing-recognizable and $L_b$ contains (or equal to) La, then $L_b$ is recognizable. I'd love to get a hint or a direction Thanks ...
The set of Turing machines that recognize $\{00, 01\}$ is undecidable
$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use ...