Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

6

You do not yet understand what Turing completeness means. Turing completeness is the ability to perform arbitrary finite computations. To simplify matters, we say an arbitrary finite computation is an effective procedure that, given some (finite) input, produces some (finite) output, after some (finite number of) steps. To simplify matters further, we ...

3

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part. Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L_1 = L_2 \cup \lbrace a \rbrace.$$ Now it is obvious ...

3

Do we ever take into consideration a word with infinite length during such analysis? Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite. Here is a more formal restatement/understanding of the problem in the question. \begin{align}\text{... 3 There are two important misunderstandings in your question. You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it. If a Turing machine decides a language L then, by definition, it accepts every input in L ... 3 You are correct. The problem of deciding "L is a recursively enumerable language" is undecidable. However, that does not make L itself undecidable. Do not mistake a language for its class! Telling whether L is in a class is definitely not the same as deciding membership in L. 2 "Turing complete" is defined as "able to do everything a Turing machine can do, if you give it enough resources". All modern programming languages are either Turing complete or "effectively" (*) Turing complete, simply because it's hard to be a useful programming language without that. In particular, if you have… Some basic means of doing arithmetic, like ... 2 No, the converse direction does not hold: Pick some non-c.e. set B \subseteq \mathbb{N}. Now consider \Gamma = \{A \ c.e. \mid A \cap B \neq \emptyset\}. By construction, \Gamma satisfies the conclusion of Rice-Shapiro (it suffices to consider singleton sets rather than all finite sets). However, for the resulting index set I we find that B \leq_m ... 2 Let us express L slightly more precisely. L=\{<TM>\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\} Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated ...

2

You have been going well. Yes, $L_3=L_1\cap L_2\in\text{ RE}$. Could it be that $L_3$ is recursive? The answer is not necessarily. There are several cases here. If $L_1$ is a recursive language as well, then $L_3$ is also recursive. If $L_1$ is not a recursive language, then $L_3$ may or may not be recursive. For example, let $L_2$ be the languages of ...

2

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,... is an enumeration of all ...

2

Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.

2

As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$. The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$. Here is the ...

2

Nice question. Notations and terms $M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs. $L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere. ...

1

How do we know that $MIN_{\mathrm{TM}}$ is inifinite? There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description. Why $C$ is equivalent to $D$? Because of point 3., which essentially forces $C$ and $D$ to have the same ...

1

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) : w \in a^*b^*| \geq k \}$ Now we want to find whether $L$ is $RE$ or not. Yes, indeed your interpretation of language $L$ is wrong. $L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$. So, now it's ...

1

A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.

1

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.

1

The classic technique of dovetailing can be used to show the complement of $L$, $\{\langle M\rangle : M\text{ is a TM that accept }010\}$ is recursively enumerable. Check this answer for details. Since $L$ is not decidable as shown by Rice's theorem, $L$ cannot be recursively enumerable. Exercise. Show that $\{\langle M\rangle : M\text{ is a TM that accept ... 1 If I can show that$A_{TM}$is mapping reducible to$L_{=2}$, ... That is a nice idea. Given$\langle M, w \rangle$, can you construct a TM$M_1$that accepts only one word, the word$w$if and only if$M$accepts$w$? Then, can you change$M_1$so that it accepts another word that is different from$w$? You can also show that$A_{TM}$is mapping ... 1 What is the Halting on all inputs problem? It is the problem about the language$TOTAL=\{⟨M⟩\mid M \text{ is a TM and }M\text{ halts on all inputs} \}$. What are all inputs? Let us fix$\Sigma$, the set of input symbols for Turing machines. The set of all inputs is$\Sigma^*$, the Kleene star of$\Sigma$. Let$E$be a Turing machine that computes a one-one ... 1 Turing completeness is a property of computational machinery/model (e.g. a programming language). Undecidability is a property of a decision problem (e.g. set membership). You may not, for some reason, like the usage of word “complete”, but both of the terms we are talking about have clear definitions that don’t rely on each other. You could think of it as ... 1 Sure: the Halting language (sometimes called$K$) is recursively enumerable whereas its complement ($\overline{K}\$) is famously not. Generally speaking, the existence of such languages follows from the implication you state -- the complement of enumerable yet undecidable languages can not be enumerable -- by the existence of precisely enumerable yet ...

1

You're talking about the following two problems: I give you a string and ask "Is it in this recursive language?" I give you a language and ask "Is this language recursive?" You're assuming that they're the same problem, but they're not.

Only top voted, non community-wiki answers of a minimum length are eligible