Tag Info

0

I describe an NFA construction method for a non-deterministic Turing machine. Let's fix an input and fix a run of the Turing machine. Let $M$ be the maximum tape cell index visited by the run. For $1 \le i \le M$, let $1 \le k_i \le K$ be the number of times tape cell $i$ is visited, where $K$ is the maximum visit count. The head movement of the Turing ...

0

00 is starting position. (evenx) [even represents parity of number of bits so far the automaton read and x is remainder of present state] oddx [odd represents parity of number of bits so far the automaton read and x is remainder of present state]

7

When you read a number $b_0 \ldots b_{n-1}$ from the LSB to the MSB, its remainder modulo 3 is \begin{align} &b_0 + 2b_1 + 4b_2 + 8b_3 + 16b_4 + 32b_5 + \cdots \bmod 3 \\ = \, &b_0 - b_1 + b_2 - b_3 + b_4 - b_5 + \cdots \end{align} In other words, when reading bits with even indices, the remainder modulo 3 increases by the bit read; and when reading ...

0

Reminder: a family $S_1, …, S_n$ is a partition of $S$ if and only if it verifies three properties: for each $i$, $S_i \neq \emptyset$; for $i \neq j$, $S_i\cap S_j = \emptyset$; $\bigcup\limits_{i=1}^nS_i = S$. I will give you hints for each of those points: the first point is proved using the fact that each state $q\in Q$ is reachable from $q_s$; the ...

1

This is a proof by contradiction. If you're not familiar with proof by contradiction, I suggest learning about that proof method (and more generally, refreshing your knowledge of discrete mathematics and proof techniques) before trying to understand this specific proof. You can think of it this way: either $M$ exists, or it doesn't. If $M$ does exist, you ...

2

The automaton accepts exactly the strings that contain exactly one occurrence of $00$ as a substring. The above is the simplest description of the automaton in English. Note that $00$ substring can be at the very beginning of a string or at the very end of a string.

5

No. The difference between a Turing machine and a finite automaton is in the amount of available work space: Finite automata are equivalent to Turing machines with finite tapes. Indeed, any finite automaton can be encoded as a Turing machine that requires no additional work tape. Conversely, a Turing machine whose work tape has finitely many cells has a ...

2

It depends what you mean by "pure". Without knowing what you mean by it, it seems hard to say. See https://en.wikipedia.org/wiki/Pure_function for one possible meaning. That notion relates to the input-output behavior of the system, and Turing machines and finite-state automata can be viewed as systems that meet those requirements. It is true ...

Top 50 recent answers are included