COMP3630 / COMP6363 week 5: Introduction to Turing Machines This Lecture Covers Chapter 8 of HMU: Introduction to Turing Machines slides created by: Dirk Pattinson, based on material by Peter Hoefner and Rob van Glabbeck; with improvements by Pascal Bercher convenor & lecturer: Pascal Bercher The Australian National University Semester 1, 2025 Content of this Chapter

Turing Machine Extensions of Turing Machines Restrictions of Turing Machines Extensions of PDAs – and Relationship to TMs Additional Reading: Chapter 8 of HMU. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 2 / 34 Introduction to TMs Introduction to TMs Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 3 / 34 Introduction to TMs Turing Machine: Informal Definition Finite Control B B B B BBa bc a b b · · ·· · · ∠ A tape extending infinitely in both sides ∠ A reading head that can edit tape, move right or left ∠ A finite control ∠ A string is accepted if finite control ever reaches a final/accepting state Heads-up: There are many variations of TMs (e.g., in COMP1600, the head could also stay stationary), and we will go through a few of them. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 4 / 34 Introduction to TMs Turing Machine: Formal Definition A Turing machine M = (Q,Σ,Γ, δ, q0,B,F ) is comprised of: ∠ Q: finite set of states ∠ Σ: finite set of input symbols ∠ Γ: finite set of tape symbols such that Σ ⊆ Γ ∠ δ: (deterministic) transition function. δ is a partial function over Q × Γ, where the first component is viewed as the present state, and the second is viewed as the tape symbol read. If δ(q,X ) is defined, then Present state Next StateTape symbol Reading head direction to move next ‹(q;X) = (q0; Y; D) The symbol replacing X ∠ B ∈ Γ \ Σ is the blank symbol. All but a finite number of tape symbols are Bs. ∠ q0: the initial state of the TM. ∠ F : the set of final/accepting states of the TM. ∠ Head always moves to the left or right. Being stationary is not an option. It can also be defined with such an option, see tutorial. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 5 / 34 Introduction to TMs Describing TMs ∠ Turing machines can be defined by describing δ using a transition table. ∠ They can also be defined using transition diagrams (with labels appropriately altered) q q0If ‹(q;X) = (q0; Y; D) X=Y D A TM that accepts any binary string that does not contain 111 q0 1= 1 ! 1=1! 1=1! 0=0! 0= 0 ! q1 q2q3 qf B=B ! B=B ! B =B ! 0=0! This encodes a DFA (almost). Can you see why? Because we never manipulate the tape and terminate once the String is read. The only difference is that not all edges are defined, but this can be fixed with a trap state. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 6 / 34 Introduction to TMs Instantaneous Descriptions of TMs ∠ An instantaneous description (or configuration) of a TM is a complete description of the system that enables one to determine the trajectory of the TM as it operates. ∠ The instantaneous description or configuration or ID of a TM contains 3 parts: (a) The (finite, non-trivial) portion of tape to the left of the reading head; (b) the state that the TM is presently in; and (c) the (finite, non-trivial) portion of the tape to the right of the reading head. q B B X1 X2 X3 X‘· · · · · · · · ·· · · Xi 1  i  ‘ head q B B X1 X2 X3 · · · · · ·· · · X‘ B B B B z }| {i Blanks segment to the strict leftz }| { X1 · · ·Xi1 statez}|{ q segment from the head onwardsz }| { Xi · · ·X‘ segment to the strict leftz }| { X1 · · ·X‘Bi1 statez}|{ q head · · · q B BX1 X2 X3 · · ·· · · X‘B B z }| { head · · · i Blanks · · · statez}|{ q segment from the head onwardsz }| { BiX1 · · ·X‘ IDState, Tape contents, Reading head location Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 7 / 34 Introduction to TMs ‘Moves’ of a TM ∠ Just as in the case of a PDA, we use ⊢ M to indicate a single move of a TM M, and ∗ ⊢ M to indicate zero or a finite number of moves of a TM. Next IDPresent ID X1 · · ·Xi1qXi · · ·X‘ X1 · · ·X‘Bi1q qBiX1 : : : X‘ Transition ‹(q;Xi ) = (q 0; Y; R) ‹(q;Xi ) = (q 0; Y; L) X1 · · ·Xi1Y q0Xi+1 · · ·X‘ X1 · · ·Xi2q0Xi1Y Xi+1 · · ·X‘ ‹(q;B) = (q0; Y; R) ‹(q;B) = (q0; Y; R) ‹(q;B) = (q0; Y; L) ‹(q;B) = (q0; Y; L) X1 · · ·X‘Bi1Y q0 (1 < i < ‘) X1 · · ·X‘1q0X‘Y i = 1 X1 · · ·X‘Bi2q0BY i > 1{ Y q0X2 · · ·X‘ i = 0 Y q0Bi1X1 · · ·X‘ i > 0{ q0BY Bi1X1 · · ·X‘ i > 0 q0BY X2 · · ·X‘ i = 0{ Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 8 / 34 Introduction to TMs Language accepted by a TM ∠ A string w is in the language accepted by a TM M iff q0w ∗ ⊢ M αpβ for some p ∈ F . For accepted words, note that the TM may not necessarily halt (i.e., allow for no further transitions) in such a final state; it may even move to a non-final state afterwards. If a final state is ever visited, w is accepted in the language of M. It is always possible to redesign a TM to halt for all accepted words without changing its language; just remove all transitions out of final states. ∠ Otherwise, w is rejected by M. Careful: Rejection might be defined differently in different textbooks/courses. (In fact, our textbook doesn’t even define it! It just “uses” it.) We will learn that we can’t always notice whether a word is rejected, because the TM might be stuck in a loop (and we don’t know that). In general, we cannot redesign TMs to halt on all rejected words. ∠ A language L is recursively enumerable if it is accepted by some TM. ∠ A language L is recursive if it is accepted by a TM that always halts on all inputs. Re cu rsi veRegular Co nte xt- fre e Re cu rsi ve ly En um er ab le (R E) (Context-sensitive languages sit between the CFLs and recursive languages.) Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 9 / 34 Introduction to TMs On Acceptance, Rejection, Halting, and Decidability Usually, there is no need to define outgoing transitions for final states, since as soon as we enter a final state, the input word is accepted (so why proceed?) ∠ Thus, when you pick/design a TM to accept a given language L, you can consider “reasonable” TMs that always halt on accepted words. ∠ However, if you have to judge properties of a given TM (e.g., whether it always halts, or accepts a particular word etc.), then you have to deal with any TM – reasonable or not... (Motivation: You might want to judge properties of somebody’s “program”) Let L be given and M a TM, such that L(M) = L. ∠ If M halts on all inputs in Σ∗, we call it a total TM, say that it decides L, and call L a decidable (or recursive) language. ∠ If M halts on all inputs taken from L (but does not necessarily halt for all inputs in Σ∗ \ L), then L is semi-decidable (or recursively enumerable). ∠ In both cases, M ‘accepts’ L. (That’s literally what L(M) = L means!) ∠ Note: Just because L ∈ RE does not mean L /∈ R since R ⊆ RE . Also, R ⊊ RE . Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 10 / 34 Introduction to TMs On Acceptance, Rejection, Halting, and Decidability ∠ “Accepting w”, i.e. w ∈ L(M), does not imply halting, since the machine may keep going after reaching a final state. If we design a TM, there’s no point in defining transitions out of any final state (so, it would halt). ∠ “Rejecting w”, i.e. w /∈ L(M), also does not imply halting. Either w was rejected because the TM halted after a finite number of steps having never reached a final state, or the TM loops through non-final states forever (and never reached a final state before). ∠ “Not accepting w” is the same as “rejecting w .” ∠ “Not rejecting w” is the same as “accepting w .” ∠ “Halting on w” neither implies w ∈ L(M) nor w /∈ L(M), i.e., it is not enough information to determine whether w was accepted or rejected. This is because we do not know whether we have previously traversed a final state. ∠ “Not halting on w” also neither implies w ∈ L(M) nor w /∈ L(M). Those are determined by whether the TM ever traverses a final state. However, if the TM is “reasonable”, then w /∈ L(M) (i.e., the word is rejected). Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 11 / 34 Introduction to TMs On Acceptance, Rejection, Halting, and Decidability Accepted w ∈ L(M) Rejected w /∈ L(M) Halted on w reached a final state, possibly kept going, then eventually reached a point where no further transition was possible eventually reached a point where no further transition was possible and never traversed a final state Looped forever on w reached a final state and keeps making transitions forever keeps making transitions forever, traversing non-final states only Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 12 / 34 Extensions of TMs Extensions of TMs Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 13 / 34 Extensions of TMs Multiple-Track TMs Multiple-track TM ∠ We do not provide a formal definition (but assume you could provide one). ∠ There are k tracks, each having symbols written on them. They are essentially tapes, but we call them that way since they are not independent. ∠ The machine can only read symbols from each tape corresponding to one location, i.e., all symbols in a column at any one time. ∠ Likewise, all tapes move simultaneously in the same direction. Finite Control · · ·· · · · · ·· · · · · ·· · · ... X1 X2 Xk ∠ A k-track TM with tape alphabet Γ has the same language-acceptance power as a TM with tape alphabet Γk . (E.g., each cell contains the “symbol” (X1, . . . ,Xk)) Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 14 / 34 Extensions of TMs Multi-tape TMs Multiple-tape TM ∠ We (again) don’t provide a formal definition (but assume you could provide one). ∠ There are k (independent) tapes, each having symbols written on them. ∠ The machine can read each tape independently, i.e., the symbols read from each tape need not correspond to the same location. ∠ After all tapes are read, all tape transitions must happen (now we can also stay with a head – the entire TM is for convenience anyway!). Finite Control · · ·· · · · · ·· · · · · ·· · · ... X1 X2 Xk ∠ The rest stays the same (e.g., one set of states, acceptance, etc.). Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 15 / 34 Extensions of TMs Multi-tape TMs Theorem 8.2.1 Every language that is accepted by a multi-tape TM is also recursively enumerable (i.e., accepted by some ‘standard’ TM). Proof of Theorem 8.2.1 ∠ Let L be accepted by a k-tape TM M. We’ll devise a 2k-track TM M ′ that accepts L. ∠ Every even tape of M ′ has the same alphabet as that of the k-tape TM. The 2i th track of M ′ contains exactly the same contents as the i th tape of M. ∠ Every odd track has an alphabet {B, †}, and contains a single †. The 2i − 1th track of M ′ contains † at the location where the i th head of M is located. Finite Control Finite Control · · ·· · · · · ·· · · · · ·· · ·· · · 10 11 54 1312 6 14 † 12 † † 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 M 0 M · · ·· · · Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 16 / 34 Extensions of TMs Multi-tape TMs Proof of Theorem 8.2.1 (1 of 3) What is the main problem we need to solve? ∠ In the Multi-tape TM M, heads move independently, whereas in the Multi-track TM M ′ they do not. So the heads can diverge: Finite Control Finite Control · · ·· · · · · ·· · · · · ·· · ·· · · 10 11 54 1312 6 14 † 12 † † 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 M 0 M · · ·· · · (But M ′ has just a single head position!) So, how to solve it? ∠ Make sure that in each transition of M, we visit all heads of M ′. ∠ “Store” all head positions in a state with k (number of tapes) entries. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 17 / 34 Extensions of TMs Multi-tape TMs Proof of Theorem 8.2.1 (2 of 3) ∠ The state of M ′ has 3 components: (a) the state of M; (b) the number of †s to its head’s strict left; and (c) a k-length tuple from (Γ ∪ {?})k . ∠ At the beginning of the sweep, the head of M ′ is at the location of the leftmost † and the state of M ′ is (q, 0, [?, · · · , ?]). The head moves to the right uncovering †s and the corresponding track symbols (are stored in the third component of the state). ∠ Each move of M takes multiple moves of M ′, and is a sweep of the tape from the location of the leftmost † to that of the rightmost † and back performing the changes to tracks that M would do to its corresponding tapes. ∠ The right sweep ends when the second component is k. Finite Control Finite Control · · ·· · · · · ·· · · · · ·· · ·· · · 10 11 54 1312 6 14 † 12 † † 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 M 0 M · · ·· · · Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 18 / 34 Extensions of TMs Multi-tape TMs Proof of Theorem 8.2.1 (3 of 3) ∠ At this stage (once the i in (q, i , [γ1, · · · , γk ]) is k and all γj are set), M ′ knows the head symbols M will have read, and knows what actions to take. ∠ It then sweeps left making appropriate changes to the tracks (just like M does to its tape) each time a † is encountered. M ′ also moves the †s accordingly. ∠ The left sweep ends when the second component is zero. At this time, M ′ would have completed moving the †s and the track contents; they’ll now match those of M. ∠ M ′ then moves the state to (q′, 0, [?, · · · , ?]) and starts the next sweep if q′ is not a final state. ∠ Note that M ′ mimics M and hence the languages accepted are identical. Finite Control Finite Control · · ·· · · · · ·· · · · · ·· · ·· · · 10 11 54 1312 6 14 † 12 † † 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 M 0 M · · ·· · · Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 19 / 34 Extensions of TMs Multi-tape TMs ∠ The running time of a TM M with input w is the number of moves M makes before it halts. (If it does not, the running time is ∞). ∠ The time complexity TM : {0, 1, . . .} → {0, 1, . . .} ∪ {∞} of a TM M is defined as: ∠ TM(n) := maximum running time of M for an input w of length n symbols. Theorem 8.2.2 The time taken for M ′ in Theorem 8.2.1 to process n moves of k-tape M is O(n2). Outline of Proof of Theorem 8.2.2 ∠ In the ith move of M, any two heads of M can be at most 2i locations apart. ∠ Each sweep then requires 4i moves of M ′. ∠ Each track update requires Θ(k) time. ∠ So, n moves in M need O(n2) moves in M ′. ! ! ! !

· · · · · · Moves ofM0 n Lo ca tio n of ta pe he ad s n 0 n 2n ap ar t Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 20 / 34 Extensions of TMs Non-deterministic TMs Non-deterministic TM: δ(q,X ) is a set of triples representing possible moves. Theorem 8.2.3 For every non-deterministic TM M, there is a TM N such that L(M) = L(N). Outline of Proof of Theorem 8.2.3 ID1 ID2;1 ID2;2 ID2;k ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘ · · · · · · ID1 ID3;1 ID3;2 ID3;3 ID3;4 ‡ † ID1 ID2;1 ID2;2‡ † † · · ·† † ID2;k † ID1 ID2;1 ID2;2‡ † · · ·† † ID2;k † † † ID3;1 ID3;2ID1 ID2;1 ID2;2‡ · · ·† † ID2;k † † † † † ‡ ‡ ‡ Tape 1 (IfM does not halt at ID1) (IfM does not halt at ID1 and ID2;1) (IfM does not halt at ID1, ID2;1 and ID2;2) (N does Breadth-First exploration of IDs ofM) Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 21 / 34 Extensions of TMs Outline of Proof of Theorem 8.2.3 ∠ We can devise a 2-tape TM N that simulates M. ∠ N first replaces the content of the first tape by ‡ followed by the ID that M is initially in, which is then followed by a special symbol †, which serves as ID separator. (N uses the second tape as scratch tape to enable this operation). ∠ If the ID corresponds to a final state, N accepts (as would M). ∠ If not, N then identifies all possible choices for the next IDs for M and enters each one of them followed by † at the right end of its first tape. (Again, N uses the second tape as scratch tape to enable this operation.) ∠ N then searches for † to the right of ‡, changes the † to a ‡ (to signify that it is processing the succeeding ID), and processes that ID in the similar way. ∠ N halts at an ID iff M would at that ID. (To have halting equivalence.) ID1 ID2;1 ID2;2 ID2;k ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘ · · · · · · ID1 ID2;1 ID2;2 ID2;k ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘ · · · · · · ID1 ID3;1 ID3;2 ID3;3 ID3;4 ‡ † ID1 ID2;1 ID2;2‡ † † · · ·† † ID2;k † ID1 ID2;1 ID2;2‡ † · · ·† † ID2;k † † † ID3;1 ID3;2ID1 ID2;1 ID2;2‡ · · ·† † ID2;k † † † † † ‡ ‡ ‡ Tape 1 (IfM does not halt at ID1) (IfM does not halt at ID1 and ID2;1) (IfM does not halt at ID1, ID2;1 and ID2;2) (N does Breadth-First exploration of IDs ofM) Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 22 / 34 Restrictions of TMs Restrictions of TMs Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 23 / 34 Restrictions of TMs TM Semi-infinite Tape A TM with a semi-infinite tape is a TM that only has blanks on one of its sides, but not on the other. Phrased (slightly) more formally: A TM with a semi-infinite tape is a TM that can never move to left of the left-most input symbol. We don’t provide a formal definition, but a way of simulating this is by providing a special symbol, placed on the left of the input, and defining the transitions to always go to the right when this is read. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 24 / 34 Restrictions of TMs TM Semi-infinite Tape Theorem 8.3.1 Every recursively enumerable language is also accepted by a TM with semi-infinite tape. Outline of Proof of Theorem 8.3.1 ∠ Given a TM M that accepts a language L, construct a two-track TM M ′ as follows. ∠ The first/second tracks of M ′ are the right/left parts of the tape of M. ∠ First, write a special symbol, say † at the leftmost part of the second track; this indicates to M ′ that a left move is not to be attempted at this location. ∠ At any time, M ′ keeps track of whether M is to the right or left of its start location. If M is to the strict right of its start location, M ′ mimics M on the first track. If M is to the strict left of its start location, M ′ mimics M on second track, but with the head directions reversed. M ′ detects the start by the † symbol. ∠ It can be formally shown that M ′ accepts a string iff M accepts it. 0 11 22 BB ab b ab b † BB 12 0 1 2 · · ·· · · · · ·· · · · · · · · · · · · M 0M L$ RL$ RL$ R R$ L Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 25 / 34 Extensions of PDAs Extensions of PDAs Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 26 / 34 Extensions of PDAs Multi-stack Machines A multistack machine is a PDA with several independent stacks (i.e., one can be popping a symbol, while another is pushing a symbol). Theorem 8.4.1 Every recursively enumerable language is accepted by a two-stack PDA Outline of Proof of Theorem 8.4.1 ∠ Let each stack again contain a bottom-most start symbol. ∠ Let ID = x−3x−2x−1qx0x1x2, i.e., w = x−3x−2x−1x0x1x2, and head read reads x0 Let stack-1 contain x0x1x2 (with x0 at the top), representing the head position and the symbols to its right. Let stack-2 contain x−1x−2x−3 (with x−1 at the top), representing the symbols to the left of the head in reversed order. ∠ What if we move the head to the right? Then, ID’ = x−3x−2x−1x0q′x1x2. We can easily do this with our stacks: How should the stack now look like? stack-1: x1x2 and stack-2: x0x−1x−2x−3. But that’s just a simple pop and push! ∠ Moving to the left, and changing the symbol that’s written can be simulated as well. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 27 / 34 Extensions of PDAs Multi-stack Machines Outline of Proof of Theorem 8.4.1, cont’d ∠ Remaining problem: How to fill the stacks initially? ∠ Recall: stack-1 contains what’s right of the head and stack-2 what’s left (but reversed). ∠ Initial configuration is q0w , so stack-1 should be w and stack-2 “empty”. ∠ We achieve this by the following procedure: ∠ I.e., run to the right filling stack-2, then run back putting it on stack-1. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 28 / 34 Extensions of PDAs Counter Machines ∠ A counter machine is a multi-stack machine whose stack alphabet contains two symbols: Z0 (stack end marker) and X ∠ Z0 is initially in the stack. ∠ Z0 may be replaced by X iZ0 for some i ≥ 0 ∠ X may be replaced by X i for some i ≥ 0. ∠ A counter machine effectively stores a non-negative number. Finite Control X Z0 X X X Z0 X X X X Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 29 / 34 Extensions of PDAs Simulating a 2-Stack PDA with a 3-Counter Machine Theorem 8.4.2 Every recursively enumerable language is accepted by a three-counter machine. Key Challenge ∠ Challenges: A 2-stack PDA uses arbitrary symbols on its stacks. A counter machine can only store and manipulate numbers. We must encode a stack’s contents into a single number so that counter operations can simulate stack operations. We must implement mathematical operations in a stack to encode push and pop operations on the “single numbers”. ∠ How stacks work? counter 1 and 2 encode stacks 1 and 3 counter 3 is used for additional computations Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 30 / 34 Extensions of PDAs Encoding a Stack into a Counter Encoding Method ∠ Assign each symbol in the stack alphabet a unique number: A = 0,B = 1,C = 2, . . . ,D = 3, etc. ∠ Represent a stack as a single number using positional encoding: X = Y1 + rY2 + r 2Y3 + · · ·+ r k−1Yk where: Y1 is the top symbol, Y2,Y3, . . . are symbols below it, r = |Γ|, the size of the stack alphabet. Example ∠ Suppose the stack contains (top to bottom): B,C ,A,A,D. ∠ Let r = 4 (since the alphabet has 4 symbols). ∠ Encode as: X = 1+ 4(2) + 42(0) + 43(0) + 44(3) = 777. ∠ The counter now stores X = 777. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 31 / 34 Extensions of PDAs Simulating Stack Operations Popping the Top Symbol ∠ Extract the top symbol using X mod r : 777 mod 4 = 1 ⇒ Top symbol was B ∠ Remove it by dividing by r : X ′ = ⌊X/4⌋ = 194. ∠ The counter now stores X ′ = 194, encoding stack C ,A,A,D = 2+ 4(0) + 42(0) + 43(3) = 194. Pushing a Symbol ∠ Suppose we push symbol A onto the stack C ,A,A,D. ∠ The current stack encoding is: X = 194. ∠ Compute the new encoding: X ′ = 4 · X + 0 = 4 · 194+ 0 = 776. ∠ The counter now stores X ′ = 776, encoding stack A,C ,A,A,D: 776 = 0+ 4(2) + 42(0) + 43(0) + 44(3). Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 32 / 34 Extensions of PDAs Counter Machine Implementation ∠ Computing X mod r (extracting top symbol from stack 1 or 2): Subtract r repeatedly from the respective stack counter (1 or 2) until value is less than r . This remaining value is the top symbol. ∠ Computing X ′ = ⌊X/r⌋ (removing top symbol from stack 1 or 2): Move remainder to counter 3. Subtract remainder from stack counter. Divide stack counter by r by decrementing it while incrementing counter 3 in steps of r . ∠ Computing X ′ = rX + Z (pushing a symbol onto a stack): Copy X to counter 3. Multiply counter 3 by r by adding it to itself r times. Add Z to counter 3. Copy the result back to the respective stack counter (1 or 2). ∠ Ensuring correct stack operations: Stack 1 and stack 2 each use a separate counter. When operating on stack 1, stack 2 stays unchanged, and vice versa. Counter 3 is used only as temporary storage. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 33 / 34 Extensions of PDAs Simulating a 3-Counter Machine with 2 Counters Theorem 8.4.3 Every recursively enumerable language is accepted by a two-counter machine. Key Idea ∠ Encode three counters using prime factorization: X = 2i3j5k , (1) where i , j , k are the values of the three counters. ∠ Updates involve: Multiplying by 2, 3, or 5 to increment. Dividing by 2, 3, or 5 to decrement. Checking divisibility to test for zero. ∠ Since a second counter can store temporary results, a 2-counter machine can simulate a 3-counter machine. Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 34 / 34 51作业君版权所有