compor.txt

;; Theory of Computation - Project 2020/2021
;;  |- Turing Machine b)
;;
;; -------- Developed by: --------
;; Group 011:
;;  |-Beatriz Alves, ist193691
;;  |-Matheus Kasai, ist191627
;;  |-Nelson Trindade, ist193743
;;
;; The compor.txt machine takes two turing machines as input, separated by $ (M1$M2),
;; and returns a turing machine that joins these two machines together. That is,
;; in all places where there is YY ^ k, in the first machine,  we will replace it
;; with the initial state of the second machine.
;; This solution can be implemented in several ways. The way we chose was to add 
;; another k to the maximum of k on all turing machines. In this way, we can distinguish
;; by placing the indicator of the machine. If there are machines with different numbers 
;; of k's, we will transform the input by placing the rest with the machine identifier 
;; multiple times, for example: 
;; Q00A0Q00A1S$Q0A0Q0A1S  ->  Q000A0Q000A1S$Q110A0Q110A1S


;; -------- Examples: --------
;; input  | Q0A1Q0A1L;Q0A0YYA1S;Q0A0NNA1S$Q0A1Q0A0R;Q0A1YYA0R;Q0A1NNA0R
;; output | Q00A1Q00A1L;Q00A0Q10A1S;Q00A0NNNA1S;Q10A1Q10A0R;Q10A1YYYA0R;Q10A1NNNA0R
;; ---
;; input  | Q0A1Q0A1L;Q0A0YYA1S;Q0A0NNA1S$Q00A1Q00A0R;Q00A1YYYA0R;Q00A1NNNA0R
;; output | Q000A1Q000A1L;Q000A0Q100A1S;Q000A0NNNNA1S;Q100A1Q100A0R;Q100A1YYYYA0R;Q100A1NNNNA0R
;; ---
;; input  | Q00A1Q00A1L;Q00A0YYYA1S;Q00A0NNNA1S$Q0A1Q0A0R;Q0A1YYA0R;Q0A1NNA0R
;; output | Q000A1Q000A1L;Q000A0Q110A1S;Q000A0NNNNA1S;Q110A1Q110A0R;Q110A1YYYYA0R;Q110A1NNNNA0R


;; -------- Turing Machine: --------


;; start state
q0  ____ ____ ****  halt-accept
q0  Q___ Q___ r***  q1
q0  **** **** ****  halt-reject


;; check the number of k's in first state
;; of the first machine
q1  0___ 0k__ rr**  q1
q1  1___ 1k__ rr**  q1
q1  2___ 2k__ rr**  q1
q1  3___ 3k__ rr**  q1
q1  4___ 4k__ rr**  q1
q1  5___ 5k__ rr**  q1
q1  6___ 6k__ rr**  q1
q1  7___ 7k__ rr**  q1
q1  8___ 8k__ rr**  q1
q1  9___ 9k__ rr**  q1

q1  A___ A*** r***  q2
q1  **** **** ****  halt-reject


;; skip to second machine
q2  0___ 0___ r***  q2
q2  1___ 1___ r***  q2
q2  2___ 2___ r***  q2
q2  3___ 3___ r***  q2
q2  4___ 4___ r***  q2
q2  5___ 5___ r***  q2
q2  6___ 6___ r***  q2
q2  7___ 7___ r***  q2
q2  8___ 8___ r***  q2
q2  9___ 9___ r***  q2

q2  Q___ Q___ r***  q2
q2  A___ A___ r***  q2
q2  $___ $___ r***  q4
q2  Y___ Y___ r***  q2
q2  N___ N___ r***  q2
q2  S___ S___ r***  q2
q2  R___ R___ r***  q2
q2  L___ L___ r***  q2
q2  ;___ ;___ r***  q2
q2  **** **** ****  halt-reject


;; check the number of k's in first state of the
;; second machine and copies the inicial state
q4  Q_** Q_** rl**  q4
q4  A___ A___ **l*  q5
q4  Ak__ Ak__ *l**  q4

q4  0_*_ 0k0_ rlr*  q4
q4  1_*_ 1k1_ rlr*  q4
q4  2_*_ 2k2_ rlr*  q4
q4  3_*_ 3k3_ rlr*  q4
q4  4_*_ 4k4_ rlr*  q4
q4  5_*_ 5k5_ rlr*  q4
q4  6_*_ 6k6_ rlr*  q4
q4  7_*_ 7k7_ rlr*  q4
q4  8_*_ 8k8_ rlr*  q4
q4  9_*_ 9k9_ rlr*  q4

q4  0k__ 0k0_ rlr*  q4
q4  1k__ 1k1_ rlr*  q4
q4  2k__ 2k2_ rlr*  q4
q4  3k__ 3k3_ rlr*  q4
q4  4k__ 4k4_ rlr*  q4
q4  5k__ 5k5_ rlr*  q4
q4  6k__ 6k6_ rlr*  q4
q4  7k__ 7k7_ rlr*  q4
q4  8k__ 8k8_ rlr*  q4
q4  9k__ 9k9_ rlr*  q4
q4  **** **** ****  halt-reject


;; rewind to first state of the first machine
q5  A_*_ A_*_ **l*  q5
q5  $___ $___ l***  q5
q5  0___ 0___ l***  q5
q5  1___ 1___ l***  q5
q5  2___ 2___ l***  q5
q5  3___ 3___ l***  q5
q5  4___ 4___ l***  q5
q5  5___ 5___ l***  q5
q5  6___ 6___ l***  q5
q5  7___ 7___ l***  q5
q5  8___ 8___ l***  q5
q5  9___ 9___ l***  q5
q5  A___ A___ l***  q5
q5  Y___ Y___ l***  q5
q5  N___ N___ l***  q5
q5  S___ S___ l***  q5
q5  R___ R___ l***  q5
q5  L___ L___ l***  q5
q5  ;___ ;___ l***  q5
q5  Q___ Q___ l***  q5
q5  ____ _k__ r*r*  q6
q5  **** **** ****  halt-reject


;; convert the third tape to the number of k's
;; third tape: first state of the second machine
q6  Qk0* Qk0* *rr* q6
q6  Qk1* Qk1* *rr* q6
q6  Qk2* Qk2* *rr* q6
q6  Qk3* Qk3* *rr* q6
q6  Qk4* Qk4* *rr* q6
q6  Qk5* Qk5* *rr* q6
q6  Qk6* Qk6* *rr* q6
q6  Qk7* Qk7* *rr* q6
q6  Qk8* Qk8* *rr* q6
q6  Qk9* Qk9* *rr* q6
q6  Qk_* Qk_* *r** q6

q6  Q___ Q___ lll* q6
q6  _k0* _k0* *ll* q6
q6  _k1* _k1* *ll* q6
q6  _k2* _k2* *ll* q6
q6  _k3* _k3* *ll* q6
q6  _k4* _k4* *ll* q6
q6  _k5* _k5* *ll* q6
q6  _k6* _k6* *ll* q6
q6  _k7* _k7* *ll* q6
q6  _k8* _k8* *ll* q6
q6  _k9* _k9* *ll* q6
q6  _k_* _k1* *ll* q6

q6  ___* ___* **r*  q6
q6  __1* __0* r***  q7
q6  __0* __0* r***  q7
q6  **** **** ****  halt-reject


;; convert every state in the new number of k
q7  Q___ Q__Q rr*r  q7
q7  Qk__ Qk0Q *l**  q7

q7  Q_*_ Q_*Q rr*r  q7
q7  0k*_ 0k*_ rr*r  q7
q7  1k*_ 1k*_ rr*r  q7
q7  2k*_ 2k*_ rr*r  q7
q7  3k*_ 3k*_ rr*r  q7
q7  4k*_ 4k*_ rr*r  q7
q7  5k*_ 5k*_ rr*r  q7
q7  6k*_ 6k*_ rr*r  q7
q7  7k*_ 7k*_ rr*r  q7
q7  8k*_ 8k*_ rr*r  q7
q7  9k*_ 9k*_ rr*r  q7
q7  Ak*_ Ak*_ ****  q8
q7  **** **** ****  halt-reject


;; put the remaining spaces in output
q8  Ak*_ Ak*_ *r*r  q8
q8  A_*_ A_*_ ll*l  q9
q8  **** **** ****  halt-reject


;; replace spaces with the correct state
q9  0k*_ 0k*0 ll*l  q9
q9  1k*_ 1k*1 ll*l  q9
q9  2k*_ 2k*2 ll*l  q9
q9  3k*_ 3k*3 ll*l  q9
q9  4k*_ 4k*4 ll*l  q9
q9  5k*_ 5k*5 ll*l  q9
q9  6k*_ 6k*6 ll*l  q9
q9  7k*_ 7k*7 ll*l  q9
q9  8k*_ 8k*8 ll*l  q9
q9  9k*_ 9k*9 ll*l  q9

q9  0*** 0*** r**r  q9
q9  1*** 1*** r**r  q9
q9  2*** 2*** r**r  q9
q9  3*** 3*** r**r  q9
q9  4*** 4*** r**r  q9
q9  5*** 5*** r**r  q9
q9  6*** 6*** r**r  q9
q9  7*** 7*** r**r  q9
q9  8*** 8*** r**r  q9
q9  9*** 9*** r**r  q9

q9  Qk0_ Qk00 *l*l  q9
q9  Qk1_ Qk11 *l*l  q9
q9  Q_*Q Q_*Q r**r  q9
q9  A_** A_** ***r  q9
q9  A_*_ A_*_ ****  q10
q9  **** **** ****  halt-reject


;; skip non state
q10 0_*_ 0_*0 r**r  q10
q10 1_*_ 1_*1 r**r  q10
q10 2_*_ 2_*2 r**r  q10
q10 3_*_ 3_*3 r**r  q10
q10 4_*_ 4_*4 r**r  q10
q10 5_*_ 5_*5 r**r  q10
q10 6_*_ 6_*6 r**r  q10
q10 7_*_ 7_*7 r**r  q10
q10 8_*_ 8_*8 r**r  q10
q10 9_*_ 9_*9 r**r  q10

q10 A_*_ A_*A r**r  q10
q10 S_*_ S_*S r**r  q10
q10 L_*_ L_*L r**r  q10
q10 R_*_ R_*R r**r  q10
q10 N_*_ N_*N *r*r  q11

q10 $_*_ $_1; r**r  q7
q10 Q_*_ Q_*Q rr*r  q7
q10 ;_*_ ;_*; r**r  q10
q10 Y_1_ Y_1Y *r*r  q11
q10 Y_0_ Y_1Q *r*r  q12
q10 __1_ __1_ ***l  q14
q10 **** **** ****  halt-reject


;; replace Y in second machine with the third tape
q11 Yk** Yk*Y *r*r  q11
q11 Y_** Y_** rl**  q111
q11 Nk** Nk*N *r*r  q11
q11 N_** N_** rl**  q111

q11 A_*_ A_*_ ****  q10
q11 **** **** ****  halt-reject

;; rewind second tape
q111 Yk** Yk** *l**  q111
q111 Nk** Nk** *l**  q111
q111 Y_** Y_** r***  q111
q111 A_*_ A_*_ ****  q11
q111 N_** N_** r***  q111


;; replace Y in first machine with the third tape
q12 Yk0_ Yk00 rrrr  q12
q12 Yk1_ Yk11 rrrr  q12
q12 Yk2_ Yk22 rrrr  q12
q12 Yk3_ Yk33 rrrr  q12
q12 Yk4_ Yk44 rrrr  q12
q12 Yk5_ Yk55 rrrr  q12
q12 Yk6_ Yk66 rrrr  q12
q12 Yk7_ Yk77 rrrr  q12
q12 Yk8_ Yk88 rrrr  q12
q12 Yk9_ Yk99 rrrr  q12

q12 Ak0_ Ak00 *rrr  q12
q12 Ak1_ Ak11 *rrr  q12
q12 Ak2_ Ak22 *rrr  q12
q12 Ak3_ Ak33 *rrr  q12
q12 Ak4_ Ak44 *rrr  q12
q12 Ak5_ Ak55 *rrr  q12
q12 Ak6_ Ak66 *rrr  q12
q12 Ak7_ Ak77 *rrr  q12
q12 Ak8_ Ak88 *rrr  q12
q12 Ak9_ Ak99 *rrr  q12
q12 A___ A___ *ll*  q13
q12 **** **** ****  halt-reject


;; exit q12 with the right start number
q13 Ak*_ Ak*_ *ll* q13
q13 A_1_ A_0_ **** q10
q13 A___ A___ **r* q13
q13 **** **** **** halt-reject


;; rewind to the start of the output
q14 __*$ __*$ ***l  q14
q14 __*0 __*0 ***l  q14
q14 __*1 __*1 ***l  q14
q14 __*2 __*2 ***l  q14
q14 __*3 __*3 ***l  q14
q14 __*4 __*4 ***l  q14
q14 __*5 __*5 ***l  q14
q14 __*6 __*6 ***l  q14
q14 __*7 __*7 ***l  q14
q14 __*8 __*8 ***l  q14
q14 __*9 __*9 ***l  q14
q14 __*A __*A ***l  q14
q14 __*Y __*Y ***l  q14
q14 __*N __*N ***l  q14
q14 __*S __*S ***l  q14
q14 __*R __*R ***l  q14
q14 __*L __*L ***l  q14
q14 __*; __*; ***l  q14
q14 __*Q __*Q ***l  q14
q14 __1_ __1_ ***r  halt-accept
q14 **** **** ****  halt-reject