New answers tagged

1

Consider a context-free grammar $\mathcal{G}$ for $L(A)$ in Greibach normal form with no useless nonterminals (i.e., non-terminals that cannot be transformed into a sequence of only terminals by applying production rules). Such a grammar can be mechanically constructed from $A$. Now build a directed graph $G = (V,E)$ as follows: Each nonterminal of $\...


0

Let $K$ be the set of indices of Turing machines which halt on the empty input. Consider the following language: $$X = \{ 0 w : |w| \in K \} \cup \{ 1 w : |w| \notin K \}. $$ You can check that neither $X$ nor its complement are recognizable. Therefore your proof idea doesn't work. Here is a different idea. Let $w_1,w_2,w_3,\ldots$ be the words in $L$, ...


3

Yes, in fact one can show that there are uncountably many languages (say by representing a language as a sequence of the form $\{0, 1\}^\mathbb N$ which can be interpreted as the binary form of some real number in $[0, 1]$) while there are only countably many TMs (as any TM can be represented by a finite string), so almost all languages are undecidable, i.e. ...


2

(For the below, I referred extensively to this github repo as well as private communication with @aozgaa) Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position $w$ in an ILB $A$ means that the $w$th string in $\...


2

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (...


0

Suppose that $x = x_1 \cdots x_n$, where $|x_i| = k$, and there exists some $z \in \{0,1\}^k$ such that $x_i \neq z$ for all $i$. We can encode $x$ by first listing $z$, and then encoding each $x_i$ using $\log_2 (2^k-1)$ fractional bits. The program also needs to know $n$. This shows that $$ K(x) \leq \log_2 (2^k-1) \cdot n + C_k + O(\log n), $$ where $C_k$ ...


2

The goal we really want is a total impossibility result: There is no reasonable model of computation which can solve its own halting problem. Church's thesis says that all the usual models (Turing machines, $\mu$-recursion, Python, etc.) are appropriately equivalent and so a proof in any one system should be convincing. However, initially at least we might ...


0

A really simple example is $A_\mathrm{TM}$ (i.e. the language of $\langle M, w \rangle$ where TM $M$ accepts $w$) and its complement $\overline{A_\mathrm{TM}}$. $A_\mathrm{TM}$ is recognizable but not decidable, while $\overline{A_\mathrm{TM}}$ is not even recognizable (if it were, then $A_\mathrm{TM}$ would be decidable!). Clearly, $A_\mathrm{TM}$ is not ...


3

You could totally do that, but there are some consequences it's worth being aware of. TM proofs only show difficulty of the halting problem for TMs, but here's a crucial thing that you might be overlooking: it is easy to implement a simulator of a TM in any language of one's choice. That can probably be done in a few dozen lines of code and it is ...


1

The first part of the disjunction is for stating that the next "state/m-configuration" of the machine is the one established in $Inst(q_i, S_j, S_k, L, q_l)$ (in case z takes as value the next cell of y', i.e., y), the second part of the disjunct is used to say that the part of the tape not scanned by the machine preserves its value.


1

Suppose a computable mapping reduction $t: \Sigma^* \to \Sigma^*$ from $EQ_{TM}$ to $\overline{EQ_{TM}}$ exists. We want to create TM's $A,B$ such that for $\langle A', B' \rangle = t(\langle A,B \rangle)$, we have \begin{align} L(A) &= L(A') \\ L(B) &= L(B') \end{align} We will nest the recursion theorem to accomplish this goal. Our "...


1

Example 1. The empty language is recognizable and its complement (the language containing all the words) is also recognizable. Example 2. Any regular language is recognizable and, since regular languages are closed under complement, its complement is also recognizable. Example 3. The language $H = \{ \langle T, x \rangle : T \mbox{ is a Turing Machine}, x \...


0

That is false. Consider for example the alphabet $\Sigma = \{0,1\}$ and the two languages $A = \emptyset$ and $B = \Sigma^*$. Clearly both $A$ and $B$ are decidable (by the trivial algorithms that always reject and always acccept, respectively) but it is false that $A \le_m B$.


0

Suppose $EQ_\mathrm{TM} \leq_\mathrm{m} \overline{EQ_\mathrm{TM}}$. Then there exists an $f : \Sigma^\star \rightarrow \Sigma^\star$ such that $f(w) \in EQ_\mathrm{TM}$ if and only if $w \in \overline{EQ_\mathrm{TM}}$. Without loss of generality, we can assume $f(w)$ is always a pair $\langle M_1, M_2 \rangle$ of TMs, as opposed to gibberish in the case that ...


4

I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting problem). This directly implies that TMs can't approximate any classical continuous function arbitrarily well. E.g. you could create the number $$\xi = \sum_{i ...


2

The usual definitions of Turing machines are given in terms of formal semantics. For instance, the Wikipedia definition describes Turing machines in precise mathematical formalism. If you are looking for something even more formal, have a look at this Coq formalization of Turing machines.


4

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer. Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i ...


0

This is just equivalent to the class of RE problems (strictly RE\R). So one example would be finding whether a Diophantine equation has a solution. A program could "solve" this problem by iterating through all possible combinations of variables, and testing them. If a solution exists, the program halts and returns yes. If a solution doesn't, the ...


0

As explained, the two formalisms are equivalent, as well as many other variations of Turing machine formalisms, so in a sense it doesn't matter. But, if you want to 'program' a Turing machine, if you are using a single-tape machine, I guess having S is okay but kinda pointless: at some point you should move your head, so why don't you do that right now? On ...


0

Think first that 'will my program halt?'. If you are sure that yes, your TM will definitely HALT then go for any searching algorithm, no problems at all. But, if are not sure about the HALTING issue, then? A TM is an idealized computer because the amounts of time and tape memory that it is allowed to use are unbounded. When it falls in ‘loops’ it may run for ...


0

Okay I can't draw and the only tools for visualizing Turing machines aren't the most practical so I'll give you a list of states and how they behave. Note that next refers to the next state and that if next and write aren't assigned the machine doesn't move to another state / doesn't write something. A brief verbal description since the machine is somewhat ...


2

Welcome to CS.SE! I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions. Ultimately this is done to have a nice definition in the sense that the class of context-sensitive languages forms a proper superset of the class of context-free languages. Definitions excluding the empty ...


0

From Savitch's theorem: A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic $[L(n)]^2$-tape bounded Turing machine, provided $L(n) \geq \log_2 n$. Thus, in particular, every context-sensitive language can be recognized within deterministic storage $n^2$, where $n$ is the length of the input. The context-sensitive languages ...


2

The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing machine using space $s(n)$ to a deterministic one using space $O(s(n)^2)$, and this is suspected to be tight in general; see for example this question on ...


18

You are right to be confused! The problem is that different authors disagree on the definition of a Turing machine. There is actually no one "right" answer. Some authors define that the machine moves L / R; but others define that it moves L / S / R, as you have pointed out. This is not the only thing that different definitions of a Turing machine ...


3

"A good driver drives in three cars. His own car, the car behind him, and the car in front of him". (Bertold Brecht). "Lookahead" is what you do when you drive a car. You look ahead and make decisions not just based on things around you, but also based on things ahead of you. A parser with a lookahead of 1 makes decisions based on the ...


Top 50 recent answers are included