Yellow means they can be changed as required.

  1. Next State
    image
    Input State Input Symbol Output State Output Symbol Action
    S0 i0 S1 i0 0
  2. If then else
    image
    Input State Input Symbol Output State Output Symbol Action
    S0 i0 S1 i0 0
    S0 i1 S2 i1 0
  3. empty Loop
    S0: initial
    S1: loop body start
    S2: loop body end 
    image

    Turing machine Tape Initials:        image

    Input State Input Symbol Output State Output Symbol Action
    S0 0 S1 1 R
    S0 1 S1 2 R
    S0 S1 R
    S0 n-1 S1 n R
    S0 n Sout    
    S1 !FlagS1 S1 FlagS1 0
    S1 FlagS1 S2   R
    S2 any S2   L
    S2 FlagS1 S0 !FlagS1 L
  4. Loop with something between S1 and S2
    Take a look at the red entry at above table, modify S2 to others, and make sure there is a new entry of returning to S2 after ur loop body logic
    Input State Input Symbol Output State Output Symbol Action
    S1 FlagS1 Others   R
      S2   R
    S2 any S2   L
    S2 FlagS1 S0 !FlagS1 L
  5. Copy of A String 111…111
    Input State Input Symbol Output State Output Symbol Action
    S0 0 Sout    
    S0 1 S1 Flag R
    S1 1 S1   R
    S1 0 S2   R
    S2 1 S2   R
    S2 0 S3 1 L
    S3 any-Flag S3   L
    S3 Flag S0 1 R
  6. Append a String 111…111 to a String 111…111||null 
    identical to 5,here is its flow graph
    image
  7. Multiplication
    sample:
     image

    Input State Input Symbol Output State Output Symbol Action Comment
    S0 0 Sout     exception
    S0 1 S1   R  
    S1 0 S6   R S6=start moving to the end and add the tailing 1
    S1 1 S2 Flag R  
    S2 1 S2   R  
    S2 0 S3   R complete reading 1st number
    S3 0 Sout     exception
    S3 1 S4   R  
    S4   S5     append following 1s to subsequent 1s
    S5 any-Flag S5   L  
    S5 Flag S1 1 R  
    S6 1 S7   R  
    S6 0 Sout     exception
    S7 1 S7   R  
    S7 0 S8   R complete reading 2nd number
    S8 1 S8   R  
    S8 0 Sout 1   normal
Advertisements