CS637 - Quiz 2

Theory of Computation
Instructor: Dr. Debasish Pattanayak
Instructions
  • Attempt all questions.
  • Show complete reasoning.
  • A computation halts if no transition is defined for the current configuration.
  • Tape alphabet: \(\{0,1,B\}\), where \(B\) is blank
  • States: \(\{q_0,q_1,q_2\}\), start state \(q_0\)
  • Transition form: \((q,a)\to(p,b,D)\), where \(D\in\{L,R\}\)
Q1 Matchings and Halting Behavior
Match entries from Column A with Column B to construct a transition subset.
Column AEntry
A1\((q_0,0)\)
A2\((q_0,1)\)
A3\((q_1,0)\)
A4\((q_1,B)\)
A5\((q_2,1)\)
Column BEntry
B1\((q_1,1,R)\)
B2\((q_0,0,R)\)
B3\((q_2,0,L)\)
B4\((q_2,1,R)\)
B5\((q_0,1,L)\)
B6\((q_1,B,R)\)
Choose five matchings to form a one-to-one transition subset.

Input strings: \(0,1,01,001,111\).
  1. For each one-to-one matching between Column A and a 5-element subset of Column B, determine whether the machine halts on each input string.
  2. Identify all matchings for which the machine halts on every input.
  3. Identify all matchings for which the machine halts on at least one input but not all.
Solution Total one-to-one matchings: \[ \binom{6}{5}\cdot 5! = 6\cdot 120 = 720. \] Exhaustive simulation over the five required inputs gives:
CategoryCount
Halts on all inputs \(\{0,1,01,001,111\}\)561
Halts on at least one but not all inputs159
Halts on none of the five inputs0
Outcome signatures for the 159 partial-halting matchings:
Signature in order \((0,1,01,001,111)\)Count
N H H H H50
H N H H H36
H H N N H24
H H H H N20
H N N N H12
H H N H H12
N H H H N4
H H H N H1
Here, \(H=\) halts, \(N=\) non-halting (cycle or unbounded drift).
Full list of all 159 partial-halting matchings 
001. A1->B1 A2->B4 A3->B2 A4->B3 A5->B5 | non-halt on 111
002. A1->B1 A2->B4 A3->B3 A4->B2 A5->B5 | non-halt on 111
003. A1->B1 A2->B4 A3->B5 A4->B3 A5->B2 | non-halt on 0
004. A1->B1 A2->B5 A3->B4 A4->B3 A5->B2 | non-halt on 0
005. A1->B2 A2->B4 A3->B1 A4->B3 A5->B5 | non-halt on 111
006. A1->B2 A2->B4 A3->B3 A4->B1 A5->B5 | non-halt on 111
007. A1->B2 A2->B5 A3->B1 A4->B3 A5->B4 | non-halt on 01,001
008. A1->B2 A2->B5 A3->B1 A4->B4 A5->B3 | non-halt on 01,001
009. A1->B2 A2->B5 A3->B3 A4->B1 A5->B4 | non-halt on 01,001
010. A1->B2 A2->B5 A3->B3 A4->B4 A5->B1 | non-halt on 01,001
011. A1->B2 A2->B5 A3->B4 A4->B1 A5->B3 | non-halt on 01,001
012. A1->B2 A2->B5 A3->B4 A4->B3 A5->B1 | non-halt on 01,001
013. A1->B3 A2->B4 A3->B1 A4->B2 A5->B5 | non-halt on 111
014. A1->B3 A2->B4 A3->B2 A4->B1 A5->B5 | non-halt on 111
015. A1->B1 A2->B2 A3->B3 A4->B6 A5->B4 | non-halt on 0
016. A1->B1 A2->B2 A3->B4 A4->B6 A5->B3 | non-halt on 0
017. A1->B1 A2->B3 A3->B2 A4->B6 A5->B4 | non-halt on 0
018. A1->B1 A2->B3 A3->B4 A4->B6 A5->B2 | non-halt on 0
019. A1->B1 A2->B4 A3->B2 A4->B6 A5->B3 | non-halt on 0
020. A1->B1 A2->B4 A3->B3 A4->B6 A5->B2 | non-halt on 0
021. A1->B1 A2->B4 A3->B6 A4->B3 A5->B2 | non-halt on 0
022. A1->B1 A2->B6 A3->B4 A4->B3 A5->B2 | non-halt on 0
023. A1->B2 A2->B1 A3->B3 A4->B6 A5->B4 | non-halt on 1,01,001
024. A1->B2 A2->B1 A3->B4 A4->B6 A5->B3 | non-halt on 1,01,001
025. A1->B2 A2->B6 A3->B3 A4->B1 A5->B4 | non-halt on 1,01,001
026. A1->B2 A2->B6 A3->B4 A4->B1 A5->B3 | non-halt on 1,01,001
027. A1->B3 A2->B1 A3->B2 A4->B6 A5->B4 | non-halt on 1
028. A1->B3 A2->B1 A3->B4 A4->B6 A5->B2 | non-halt on 1
029. A1->B3 A2->B6 A3->B2 A4->B1 A5->B4 | non-halt on 1
030. A1->B3 A2->B6 A3->B4 A4->B1 A5->B2 | non-halt on 1
031. A1->B4 A2->B1 A3->B2 A4->B6 A5->B3 | non-halt on 1
032. A1->B4 A2->B1 A3->B3 A4->B6 A5->B2 | non-halt on 1
033. A1->B4 A2->B2 A3->B3 A4->B1 A5->B6 | non-halt on 01
034. A1->B4 A2->B2 A3->B3 A4->B6 A5->B1 | non-halt on 01
035. A1->B4 A2->B3 A3->B2 A4->B1 A5->B6 | non-halt on 01
036. A1->B4 A2->B3 A3->B2 A4->B6 A5->B1 | non-halt on 01
037. A1->B4 A2->B6 A3->B2 A4->B1 A5->B3 | non-halt on 1
038. A1->B4 A2->B6 A3->B3 A4->B1 A5->B2 | non-halt on 1
039. A1->B6 A2->B2 A3->B3 A4->B1 A5->B4 | non-halt on 0
040. A1->B6 A2->B2 A3->B4 A4->B1 A5->B3 | non-halt on 0
041. A1->B6 A2->B3 A3->B2 A4->B1 A5->B4 | non-halt on 0
042. A1->B6 A2->B3 A3->B4 A4->B1 A5->B2 | non-halt on 0
043. A1->B6 A2->B4 A3->B2 A4->B1 A5->B3 | non-halt on 0
044. A1->B6 A2->B4 A3->B3 A4->B1 A5->B2 | non-halt on 0
045. A1->B1 A2->B2 A3->B3 A4->B6 A5->B5 | non-halt on 0
046. A1->B1 A2->B2 A3->B5 A4->B6 A5->B3 | non-halt on 0
047. A1->B1 A2->B3 A3->B2 A4->B6 A5->B5 | non-halt on 0
048. A1->B1 A2->B3 A3->B5 A4->B6 A5->B2 | non-halt on 0
049. A1->B1 A2->B5 A3->B2 A4->B6 A5->B3 | non-halt on 0
050. A1->B1 A2->B5 A3->B3 A4->B6 A5->B2 | non-halt on 0
051. A1->B1 A2->B5 A3->B6 A4->B3 A5->B2 | non-halt on 0
052. A1->B1 A2->B6 A3->B5 A4->B3 A5->B2 | non-halt on 0
053. A1->B2 A2->B1 A3->B3 A4->B6 A5->B5 | non-halt on 1,01,001
054. A1->B2 A2->B1 A3->B5 A4->B6 A5->B3 | non-halt on 1,01,001
055. A1->B2 A2->B5 A3->B1 A4->B3 A5->B6 | non-halt on 01,001
056. A1->B2 A2->B5 A3->B1 A4->B6 A5->B3 | non-halt on 01,001
057. A1->B2 A2->B5 A3->B3 A4->B1 A5->B6 | non-halt on 01,001
058. A1->B2 A2->B5 A3->B3 A4->B6 A5->B1 | non-halt on 01,001
059. A1->B2 A2->B5 A3->B6 A4->B1 A5->B3 | non-halt on 01,001
060. A1->B2 A2->B5 A3->B6 A4->B3 A5->B1 | non-halt on 01,001
061. A1->B2 A2->B6 A3->B3 A4->B1 A5->B5 | non-halt on 1,01,001
062. A1->B2 A2->B6 A3->B5 A4->B1 A5->B3 | non-halt on 1,01,001
063. A1->B3 A2->B1 A3->B2 A4->B6 A5->B5 | non-halt on 1
064. A1->B3 A2->B1 A3->B5 A4->B6 A5->B2 | non-halt on 1
065. A1->B3 A2->B6 A3->B2 A4->B1 A5->B5 | non-halt on 1
066. A1->B3 A2->B6 A3->B5 A4->B1 A5->B2 | non-halt on 1
067. A1->B5 A2->B1 A3->B2 A4->B6 A5->B3 | non-halt on 1
068. A1->B5 A2->B1 A3->B3 A4->B6 A5->B2 | non-halt on 1
069. A1->B5 A2->B6 A3->B2 A4->B1 A5->B3 | non-halt on 1
070. A1->B5 A2->B6 A3->B3 A4->B1 A5->B2 | non-halt on 1
071. A1->B6 A2->B2 A3->B3 A4->B1 A5->B5 | non-halt on 0
072. A1->B6 A2->B2 A3->B5 A4->B1 A5->B3 | non-halt on 0
073. A1->B6 A2->B3 A3->B2 A4->B1 A5->B5 | non-halt on 0
074. A1->B6 A2->B3 A3->B5 A4->B1 A5->B2 | non-halt on 0
075. A1->B6 A2->B5 A3->B2 A4->B1 A5->B3 | non-halt on 0
076. A1->B6 A2->B5 A3->B3 A4->B1 A5->B2 | non-halt on 0
077. A1->B1 A2->B2 A3->B4 A4->B6 A5->B5 | non-halt on 0
078. A1->B1 A2->B2 A3->B5 A4->B6 A5->B4 | non-halt on 0
079. A1->B1 A2->B4 A3->B2 A4->B6 A5->B5 | non-halt on 0,111
080. A1->B1 A2->B4 A3->B5 A4->B6 A5->B2 | non-halt on 0
081. A1->B1 A2->B4 A3->B6 A4->B2 A5->B5 | non-halt on 111
082. A1->B1 A2->B5 A3->B2 A4->B6 A5->B4 | non-halt on 0
083. A1->B1 A2->B5 A3->B4 A4->B6 A5->B2 | non-halt on 0
084. A1->B2 A2->B1 A3->B4 A4->B6 A5->B5 | non-halt on 1,01,001
085. A1->B2 A2->B1 A3->B5 A4->B6 A5->B4 | non-halt on 1,01,001
086. A1->B2 A2->B4 A3->B1 A4->B6 A5->B5 | non-halt on 111
087. A1->B2 A2->B4 A3->B6 A4->B1 A5->B5 | non-halt on 111
088. A1->B2 A2->B5 A3->B1 A4->B4 A5->B6 | non-halt on 01,001
089. A1->B2 A2->B5 A3->B1 A4->B6 A5->B4 | non-halt on 01,001
090. A1->B2 A2->B5 A3->B4 A4->B1 A5->B6 | non-halt on 01,001
091. A1->B2 A2->B5 A3->B4 A4->B6 A5->B1 | non-halt on 01,001
092. A1->B2 A2->B5 A3->B6 A4->B1 A5->B4 | non-halt on 01,001
093. A1->B2 A2->B5 A3->B6 A4->B4 A5->B1 | non-halt on 01,001
094. A1->B2 A2->B6 A3->B4 A4->B1 A5->B5 | non-halt on 1,01,001
095. A1->B2 A2->B6 A3->B5 A4->B1 A5->B4 | non-halt on 1,01,001
096. A1->B4 A2->B1 A3->B2 A4->B6 A5->B5 | non-halt on 1
097. A1->B4 A2->B1 A3->B5 A4->B6 A5->B2 | non-halt on 1
098. A1->B4 A2->B2 A3->B5 A4->B1 A5->B6 | non-halt on 01
099. A1->B4 A2->B2 A3->B5 A4->B6 A5->B1 | non-halt on 01
100. A1->B4 A2->B5 A3->B2 A4->B1 A5->B6 | non-halt on 01
101. A1->B4 A2->B5 A3->B2 A4->B6 A5->B1 | non-halt on 01
102. A1->B4 A2->B6 A3->B2 A4->B1 A5->B5 | non-halt on 1
103. A1->B4 A2->B6 A3->B5 A4->B1 A5->B2 | non-halt on 1
104. A1->B5 A2->B1 A3->B2 A4->B6 A5->B4 | non-halt on 1
105. A1->B5 A2->B1 A3->B4 A4->B6 A5->B2 | non-halt on 1
106. A1->B5 A2->B6 A3->B2 A4->B1 A5->B4 | non-halt on 1
107. A1->B5 A2->B6 A3->B4 A4->B1 A5->B2 | non-halt on 1
108. A1->B6 A2->B2 A3->B4 A4->B1 A5->B5 | non-halt on 0
109. A1->B6 A2->B2 A3->B5 A4->B1 A5->B4 | non-halt on 0
110. A1->B6 A2->B4 A3->B1 A4->B2 A5->B5 | non-halt on 111
111. A1->B6 A2->B4 A3->B2 A4->B1 A5->B5 | non-halt on 0,111
112. A1->B6 A2->B4 A3->B5 A4->B1 A5->B2 | non-halt on 0
113. A1->B6 A2->B5 A3->B2 A4->B1 A5->B4 | non-halt on 0
114. A1->B6 A2->B5 A3->B4 A4->B1 A5->B2 | non-halt on 0
115. A1->B1 A2->B3 A3->B4 A4->B6 A5->B5 | non-halt on 0
116. A1->B1 A2->B3 A3->B5 A4->B6 A5->B4 | non-halt on 0
117. A1->B1 A2->B4 A3->B3 A4->B6 A5->B5 | non-halt on 0,111
118. A1->B1 A2->B4 A3->B5 A4->B6 A5->B3 | non-halt on 0
119. A1->B1 A2->B4 A3->B6 A4->B3 A5->B5 | non-halt on 111
120. A1->B1 A2->B5 A3->B3 A4->B6 A5->B4 | non-halt on 0
121. A1->B1 A2->B5 A3->B4 A4->B6 A5->B3 | non-halt on 0
122. A1->B3 A2->B1 A3->B4 A4->B6 A5->B5 | non-halt on 1
123. A1->B3 A2->B1 A3->B5 A4->B6 A5->B4 | non-halt on 1
124. A1->B3 A2->B4 A3->B1 A4->B6 A5->B5 | non-halt on 111
125. A1->B3 A2->B4 A3->B6 A4->B1 A5->B5 | non-halt on 111
126. A1->B3 A2->B6 A3->B4 A4->B1 A5->B5 | non-halt on 1
127. A1->B3 A2->B6 A3->B5 A4->B1 A5->B4 | non-halt on 1
128. A1->B4 A2->B1 A3->B3 A4->B6 A5->B5 | non-halt on 1
129. A1->B4 A2->B1 A3->B5 A4->B6 A5->B3 | non-halt on 1
130. A1->B4 A2->B3 A3->B5 A4->B1 A5->B6 | non-halt on 01
131. A1->B4 A2->B3 A3->B5 A4->B6 A5->B1 | non-halt on 01
132. A1->B4 A2->B5 A3->B3 A4->B1 A5->B6 | non-halt on 01
133. A1->B4 A2->B5 A3->B3 A4->B6 A5->B1 | non-halt on 01
134. A1->B4 A2->B6 A3->B3 A4->B1 A5->B5 | non-halt on 1
135. A1->B4 A2->B6 A3->B5 A4->B1 A5->B3 | non-halt on 1
136. A1->B5 A2->B1 A3->B3 A4->B6 A5->B4 | non-halt on 1
137. A1->B5 A2->B1 A3->B4 A4->B6 A5->B3 | non-halt on 1
138. A1->B5 A2->B6 A3->B3 A4->B1 A5->B4 | non-halt on 1
139. A1->B5 A2->B6 A3->B4 A4->B1 A5->B3 | non-halt on 1
140. A1->B6 A2->B3 A3->B4 A4->B1 A5->B5 | non-halt on 0
141. A1->B6 A2->B3 A3->B4 A4->B5 A5->B1 | non-halt on 001
142. A1->B6 A2->B3 A3->B5 A4->B1 A5->B4 | non-halt on 0
143. A1->B6 A2->B4 A3->B1 A4->B3 A5->B5 | non-halt on 111
144. A1->B6 A2->B4 A3->B3 A4->B1 A5->B5 | non-halt on 0,111
145. A1->B6 A2->B4 A3->B5 A4->B1 A5->B3 | non-halt on 0
146. A1->B6 A2->B5 A3->B3 A4->B1 A5->B4 | non-halt on 0
147. A1->B6 A2->B5 A3->B4 A4->B1 A5->B3 | non-halt on 0
148. A1->B2 A2->B4 A3->B3 A4->B6 A5->B5 | non-halt on 111
149. A1->B2 A2->B4 A3->B6 A4->B3 A5->B5 | non-halt on 111
150. A1->B2 A2->B5 A3->B3 A4->B4 A5->B6 | non-halt on 01,001
151. A1->B2 A2->B5 A3->B3 A4->B6 A5->B4 | non-halt on 01,001
152. A1->B2 A2->B5 A3->B4 A4->B3 A5->B6 | non-halt on 01,001
153. A1->B2 A2->B5 A3->B4 A4->B6 A5->B3 | non-halt on 01,001
154. A1->B2 A2->B5 A3->B6 A4->B3 A5->B4 | non-halt on 01,001
155. A1->B2 A2->B5 A3->B6 A4->B4 A5->B3 | non-halt on 01,001
156. A1->B3 A2->B4 A3->B2 A4->B6 A5->B5 | non-halt on 111
157. A1->B3 A2->B4 A3->B6 A4->B2 A5->B5 | non-halt on 111
158. A1->B6 A2->B4 A3->B2 A4->B3 A5->B5 | non-halt on 111
159. A1->B6 A2->B4 A3->B3 A4->B2 A5->B5 | non-halt on 111
Therefore, the 561 remaining matchings are exactly those that halt on every listed input.
Q2 Restricted Subset Matchings
Use only:
Column A: \(A1,A2,A3,A5\), Column B: \(B1,B2,B4,B5\).
  1. Construct all bijective matchings.
  2. For which matchings does the machine enter a cycle on input \(01\)?
  3. For which matchings does the head move unboundedly right on input \(111\)?
Solution Number of bijections: \(4! = 24\).
All 24 bijective matchings 
1. A1->B1, A2->B2, A3->B4, A5->B5
2. A1->B1, A2->B2, A3->B5, A5->B4
3. A1->B1, A2->B4, A3->B2, A5->B5
4. A1->B1, A2->B4, A3->B5, A5->B2
5. A1->B1, A2->B5, A3->B2, A5->B4
6. A1->B1, A2->B5, A3->B4, A5->B2
7. A1->B2, A2->B1, A3->B4, A5->B5
8. A1->B2, A2->B1, A3->B5, A5->B4
9. A1->B2, A2->B4, A3->B1, A5->B5
10. A1->B2, A2->B4, A3->B5, A5->B1
11. A1->B2, A2->B5, A3->B1, A5->B4
12. A1->B2, A2->B5, A3->B4, A5->B1
13. A1->B4, A2->B1, A3->B2, A5->B5
14. A1->B4, A2->B1, A3->B5, A5->B2
15. A1->B4, A2->B2, A3->B1, A5->B5
16. A1->B4, A2->B2, A3->B5, A5->B1
17. A1->B4, A2->B5, A3->B1, A5->B2
18. A1->B4, A2->B5, A3->B2, A5->B1
19. A1->B5, A2->B1, A3->B2, A5->B4
20. A1->B5, A2->B1, A3->B4, A5->B2
21. A1->B5, A2->B2, A3->B1, A5->B4
22. A1->B5, A2->B2, A3->B4, A5->B1
23. A1->B5, A2->B4, A3->B1, A5->B2
24. A1->B5, A2->B4, A3->B2, A5->B1
Cycle on input \(01\): exactly matchings 11 and 12.

Head moves unboundedly right on input \(111\): none of the 24 matchings.
(All either halt or enter a finite cycle; no matching keeps pushing right forever.)
Q3 Matching on \(C1,C2,C3\) vs \(D1,D2,D3,D4\)
Use:
Column AEntry
C1\((q_0,0)\)
C2\((q_1,1)\)
C3\((q_2,0)\)
Column BEntry
D1\((q_1,0,R)\)
D2\((q_2,1,R)\)
D3\((q_0,0,L)\)
D4\((q_2,0,L)\)
Construct any one-to-one matching between Column A and any three entries from Column B.
  1. Prove that for every possible matching, the resulting TM does not halt on at least one non-empty input over \(\{0,1\}\).
  2. Give formal reasoning using configuration repetition or unbounded head motion.
Solution It is a trick question to test whether you can say that the machine will halt in all matchings since there is no transition on blank \(B\) for any state in this restricted system.
🏠