Turing Machine Examples

Mathematical Logic · Axiom Academy

LESSON Turing Machine Examples Constructing Turing machines to recognize languages and compute functions Mathematical Logic • Unit 6 - Computability Theory Our first example recognizes strings with equal numbers of 0s followed by 1s. This demonstrates the fundamental technique of marking and sweeping . Examples: Accept: ε, 01, 0011, 000111 | Reject: 0, 1, 001, 010 Find the leftmost unmarked 0, mark it with X Scan right to find the leftmost unmarked 1, mark it with Y Return to the beginning and repeat Accept if all symbols are marked and properly paired Example 2: TM for Palindrome Recognition A palindrome reads the same forwards and backwards. This TM recognizes binary palindromes using the technique of matching outer symbols . Examples: Accept: ε, 0, 1, 00, 11, 010, 101, 0110, 1001 | Reject: 01, 10, 001, 100 Strategy: Match Ends and Work Inward Mark the leftmost symbol (0 or 1) Scan to the rightmost unmarked symbol Check if it matches the marked symbol; if not, reject Mark the rightmost symbol and return to the left Repeat until all symbols are matched or we reach the middle Example 3: TM for Binary Addition This TM computes addition using unary representation: transforms to . Compute where inputs are in unary (tally marks) Examples: 11+111 → 11111 , 1+1 → 11 , 1111+11 → 111111 Convert the separator '+' into a '1' The result is simply the concatenation of all 1s Alternatively: mark symbols and shift to create continuous sequence

This is the written version of the interactive lesson above. See the full Mathematical Logic course.