Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

# cs2102: Discrete Math (Fall 2016)

Submitting Problem Set Omega (Sun, 27 Nov 2016)

The form for submitting Problem Set Omega is here:

Class 23: Universal Machines (Sat, 19 Nov 2016)

### Schedule

Problem Set 9 is tomorrow, Wednesday, 23 November at 6:29pm.

Problem Set Omega is now posted and due on Sunday, 4 December or Tuesday, 6 December (see problem set for details). It is not like the others, and counts as a “bonus” optional assignment.

Simple Turing Machine simulator (and XOR machine): tm.py

Dori-Mic and the Universal Machine!

## Turing Machine

$$TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \in S, q{Accept} \subseteq S)$$

$S$ is a finite set (the “in-the-head” processing states)
$\Gamma$ is a finite set (symbols that can be writte on the tape)
$\text{\em dir} = { \text{\bf Left}, \text{\bf Right}, \text{\bf Halt} }$ is the direction to move on the tape.

An execution of a Turing Machine, $TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \in S, q{Accept} \subseteq S)$, is a (possibly infinite) sequence of configurations, $(x_0, x_1, \ldots)$ where $x_i \in \text{\em Tsil} \times S \times \text{\em List}$ (elements of the lists are in the finite set of symbols, $\Gamma$), such that:

  - $x_0 = (\text{\bf null}, q_0, \text{\bf input})$
- and all transitions follow the rules (need to be specified in detail).


## Machines and Languages

A language is a (possibly infinite) set of finite strings.

$\Sigma$ = alphabet, a finite set of symbols
$L \subseteq \Sigma^{*}$

$$L_{XOR} = { x_0x_1\ldots x_n + y_0y_1\ldots y_n = z_0z_1\ldots z_n \ | x_i \in {0, 1}, y_i \in {0, 1}, z_i = x_i \oplus y_i }$$

## Turing Machine Computation

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \in S, q{Accept} \subseteq S)$, accepts a string x, if there is an execution of M that starts in configuration $(\text{\bf null}, q_0, x)$, and terminates in a configuration, $(l, q_f, r)$, where $qf \in q{Accept}$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \in S, q{Accept} \subseteq S)$, recognizes a language $L$, if for all strings $s \in L$, $M$ accepts $s$, and there is no string $t \notin L$ such that $M$ accepts $t$.

TuringMachine = namedtuple('TuringMachine', ['rules', 'q_0', 'q_accepting'])

def simulate(tm, starttape):
tape = starttape
currentstate = tm.q_0

while True:
(nextstate, writesym, dir) = tm.rules[(currentstate, readsym)]
currentstate = nextstate
else:
return currentstate in tm.q_accepting # no rule, halt

if dir == 'L':
elif dir == 'R':
if len(tape) <= headpos: tape.append('_') # blank
else: # assert dir == 'Halt'
return currentstate in tm.q_accepting

xorm = TuringMachine(
rules = { ('S', '0'): ('R0', '-', 'R'), ('S', '1'): ('R1', '-', 'R'),
('S', '+'): ('C', '+', 'R'),
('R0', '0'): ('R0', '0', 'R'), ('R0', '1'): ('R0', '1', 'R'),
('R1', '0'): ('R1', '0', 'R'), ('R1', '1'): ('R1', '1', 'R'),
('R0', '+'): ('X0', '+', 'R'), ('R1', '+'): ('X1', '+', 'R'),
('X0', 'X'): ('X0', 'X', 'R'), ('X1', 'X'): ('X1', 'X', 'R'),
('X0', '0'): ('Y0', 'X', 'R'), ('X0', '1'): ('Y1', 'X', 'R'),
('X1', '0'): ('Y1', 'X', 'R'), ('X1', '1'): ('Y0', 'X', 'R'),
('Y0', '0'): ('Y0', '0', 'R'), ('Y0', '1'): ('Y0', '1', 'R'),
('Y1', '0'): ('Y1', '0', 'R'), ('Y1', '1'): ('Y1', '1', 'R'),
('Y0', '='): ('Z0', '=', 'R'), ('Y1', '='): ('Z1', '=', 'R'),
('Z0', 'X'): ('Z0', 'X', 'R'), ('Z1', 'X'): ('Z1', 'X', 'R'),
('Z0', '0'): ('B', 'X', 'L'),  ('Z1', '1'): ('B', 'X', 'L'),
('B', '0'): ('B', '0', 'L'),   ('B', '1'): ('B', '1', 'L'),
('B', '+'): ('B', '+', 'L'),   ('B', 'X'): ('B', 'X', 'L'),
('B', '='): ('B', '=', 'L'),   ('B', '-'): ('S', '-', 'R'),
('C', 'X'): ('C', 'X', 'R'),   ('C', '='): ('C', '=', 'R'),
('C', '$'): ('Accept', '$', 'Halt') },
q_0 = 'S', q_accepting = { 'Accept' })