[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhturing_machinea.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "turing machine" source: https://www.jemoka.com/posts/kbhturing_machinea/ --- constituents \(Q\) is a finite set of states \(\Sigma\) is the input alphabet, where \(\square \not \in \Sigma\) \(\Gamma\) is the tape alphabet, where \(\square \in \Gamma\), and \(\Sigma \subseteq \Gamma\) (because we can write empty cells) \(\delta: Q \times \Gamma \to Q \times \Gamma \times \qty {L, R}\) \(q_0 \in Q\), the start state \(q_{a} \in Q\), the accept state \(q_{r} \neq q_{a}\in Q\), the reject state (because a Turing Machine may not terminate at end of input) requirements additional information why TM is awesome a Turing Machine \(M = \qty(\Gamma, Q, S)\) should be ready for inputs of any length \(n\) (in particular, when designing \(M\), we don’t know what \(n\) will be) a Turing machine’s computation is “local”—you can’t look at the whole input, and the composition of these many local steps No ambiguity as to runtime: how many times you apply \(\delta\) before you get to Qaccept or Qreject Church-Turing thesis as local steps “computation is any process that takes place in a sequence of simple, local steps.” configuration the configuration of a Turing Machine contains its entire state: the content of the tape the current state of the controller the position of the writer we write this by putting the state right before the position of the write head: this means that our write head is at the bit that says 1, at state q7. yield Let \(C_1\) and \(C_2\) be configurations of a TM \(M\); let us call \(C_1\) yields \(C_2\) if \(M\) is in configuration \(C_2\) after running \(M\) in configuration \(C_1\) for one step. Suppose \(\delta(q_1, b) = (q_2, c, L)\); then \(aa (q_{1}) bb\) yields \(a (q_{2}) a c b\). accept A TM \(M\) accepts \(w\) if there are configs \(C_0, …, C_{k}\) for which: \(C_0 = q_0w\) \(C_i\) yields \(C_{i+1}\) for \(i=0 … k-1\) and \(C_{k}\) contains \(q_{accept}\) recognize vs decide recognize \(L\): the TM will accept strings \(l \in L\) (a string outside may loop or reject) decide \(L\): the TM will accept strings \(l \in L\), and reject all strings \(l’ \not \in L\) recognizable A language \(L\) is recognizable (“recursively enumerable”) if some TM recognizes \(L\) decidable A language \(L\) is recursive if some TM decides \(L\) L is decidable IFF L and not L are both recognizable given a \(M_1\) that recognizes \(L\), a \(M_{2}\) that recognizes \(\neg L\), we want to build a machine \(M\) that decides \(L\). (this is easy; just run both machines at once on two tapes and then just check which one gets recognized first; accept if \(M_1\) accepts and reject if \(M_2\) accepts) if \(L\) is decidable, \(\neg L\) is also decidable (because we just run \(L\) and return the opposite) intuition structure finite state controller (with a write head) infinite, writable tape (whenever the machine goes to the right, we get a new cell, if we go left, we hit a wall and stay put) we lay our input onto the tape capability they can write to and read from the tape the head can move left and right the input doesn’t have to be read entirely: we can bail at any moment, or not stop at all Accept and Reject take immediate effect. Graph-based Turing Machine Representation nodes are the finite control states each edge has a three-tuple: \((read, write, move)\) which is what we are going to read, what we are going to write, and where we move on the tape (left or right) the empty cell is a valid read or write (i.e. we can read nothing, meaning our input has ended, and we can write nothing) notation: read -> write, move examples two of the same string \begin{equation} L = \qty {w \# w \mid w \in {0,1}^{*}} \end{equation} if there is no # on the tape (or more than one, #), reject while you do this, copy the entire string to the right (we do this because otherwise we wouldn’t know if moving to the left actually did something (i.e. the first symbol is duplicated) or we were just hitting the wall and bouncing) while there is a bit to the left of # replace the first bit with X, and check the first bit to the right of the # and x is the same one if not, reject; if so, replace the right bit with an X too if there is a bit to the right of # that’s not X, then reject; otherwise, accept Recognizability decidable predicate A decidable predicate \(R(x,y)\) is a proposition about the input strings \(x\), \(y\), such that some Turing machine \(M\) will implement \(R\). That is, for all \(x, y\), we have \(R(x,y)\) is true means \(M(x,y)\) accepts, and \(R(x,y)\) is false means \(M(x,y)\) rejects. That is: \(R: \Sigma^{*} \times \Sigma^{*} \to \qty {T,f}\) predicate recognizability a particular language \(A\) is recognizable IFF there is a decidable (note the upgrade in strength) predicate \(R(x,y)\) such that \(A = \qty {x \mid \exists y, R(x,y)}\). Proof: \(\Rightarrow\) assume \(A = \qty {x \mid \exists y, R(x,y)}\), we want to show that \(A\) is recognizable Create a Turing machine which: enumerate all finite-length strings \(y\); if \(R(x,y)\) is true, accept it. \(\Leftarrow\) if \(A\) is recognizable, there is some decidable predicate \(R(x,y)\) such that \(A = \qty {x \mid \exists y, R(x,y)}\). By definition \(A\) is recognizable, so there’s an \(M\) which recognizes \(A\). Define a predicate \(R(x,y)\) be TRUE IFF \(M\) accepts \(x\) in \(|y|\) steps. We now want to show that \(R(x,y)\) is decidable. If \(M\) accepts \(x\); it would have done so in some finite \(y\) steps. Hence, \(R(x,y) = TRUE\). If there is some \(y\) for which \(R(x,y)\) is true, we can see that we can run \(M\) on \(x\) for \(y\) steps and see that by definition \(M\) have just accepted the string. This is decidable because we can check for \(y\) steps exactly, so we will always terminate. Turing Machine as a universal algorithm why do we focus on a turing machine? its extremely simple to analyze (its possible to formalize and reason about it) Extended Church-Turing Thesis—every “real-world” efficiently computable algorithm can be “compiled to” efficiently computable Turing Machine with only poly-slowdown