0
votes
1answer
16 views

how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
1
vote
1answer
57 views

Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer". An idea: I thought that I would do something like ...
1
vote
1answer
21 views

Recursively Enumerable Languages and Turing Machines

L1 = { M | Turing Machine M terminates for at least 637 inputs} L2 = { M | Turing Machine M terminates for at most 636 inputs} One of them is recursively enumerable, which one?
0
votes
1answer
31 views

Accepting/rejecting states in Turing Machine

In language decidability problems, a TM halts with a halting state, an accepting state or a rejecting state. My understanding is that when a TM machines halts on accepting state, it removes everything ...
1
vote
1answer
36 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 ...
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
2
votes
0answers
64 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$ | ...
1
vote
1answer
56 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
0
votes
1answer
38 views

What does it mean for a Turing machine $M$ to accept $\epsilon$

Suppose $B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$. I do not understand what it means for $M$ to accept $\epsilon$. Can someone explain ...
3
votes
0answers
90 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 ...
1
vote
2answers
59 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
1
vote
1answer
67 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 ...
2
votes
1answer
51 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
0
votes
1answer
38 views

Assign Integer to Each Turing Machine

I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to ...
2
votes
0answers
50 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
1answer
119 views

Show that the language TOT={<M> | M is a Turing Machine that halts with all inputs} is not recursively enumerable nor its complement.

I've been thinking about how to show this but I'm stuck. I'm required to prove this: "Show that the language TOT={#M# | M is a Turing Machine that halts with all inputs} is not recursively ...
2
votes
1answer
31 views

Undecidability of REGULAR_TM

In case you have Sipser's Introduction to the Theory of Computation 3rd edition, I am asking specifically about the proof of theorem 5.3, how the language REGULAR_TM is undecidable. \begin{equation} ...
1
vote
1answer
56 views

How do you argue (or prove) that a certain Turing machine accepts a language?

I have an existing Turing machine that is essentially the same as this one here: X is the blank symbol, # is the end of the tape. The format is input/output, direction. 0 indicates failure ...
-2
votes
1answer
45 views

Probability over decidable languages

Let $\mathcal S$ be the set of all languages over some finite alphabet $\Sigma$. Prove that the probability of a randomly chosen (arbitrary distribution) language has a decider is zero.
1
vote
1answer
90 views

Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages: $1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ...
2
votes
1answer
85 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 ...
2
votes
2answers
769 views

Why is showing a language is Turing recognizable trickier than showing Turing decidable?

I have written a proof to show that a Turing Decidable languages are closed under union (amongst other things). Later, I have written a proof to show that Turing Recognizable languages are closed ...
3
votes
1answer
107 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
1
vote
1answer
71 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...