Turing Machines

Now we need to define the Turing machine.

A Turing machine is a septuple where M =(Q, Σ, Γ, δ, q0, qa, qr) where Q, Σ, Γ are all finite sets and

Q is the set of states
Σ is the input alphabet (not containing a blank character)
Γ is the tape alphabet (it mus contain all of Σ and the blank character, may also have a shadow alphabet)
δ is the transistion function (this is usually shown in the form of a state diagram)
q0 is the start state
qa is the accpet state
qr is the reject state

Most of this is in the textbook, so I'll just write up the definitions.

Definition: A Turing Machine M accepts w (a string) if there exists a sequence c1,c2,ck such that
1. c1 is the start configuration with input w
2. ci+1 is obtained from ci by δ
3. ck is an acceptin configuration

Definition: the Language of M is L(M) = {w is a member of Σ*|M accepts w}

Definition: a Language L is Turing Recognizable if there is a turing machine fuch that L = L(M)

Definition: a Language is Turing Decidable if there is a decider (a decider halts on all input) M such that L = L(M)

Note: Every decidable language is recognizable but not conversely

Note: Every finite language is decidable

New year, new you

Right so I fucked up last time and never did any fucking notes. This time I'm gonna try... tryyyy to fucking do it.

Right Computability and Complexity. Lecture 1:

Computability: The main idea of computability is which computational problems admit solution by computer i.e. Algortihmic solutions

Complexity: The main idea of complexity is which questions can be solved efficiently i.e. how resource intensive or tractable

The main idea of the whole class is to make mathematical models of computers and deduce things about them.

Definition: an Alphabet is a non-empty finite set of symbols

e.g. {1,2......,n} Σ 1
e.g. {1,a,b,x,3} Σ 2

Definition: a String (over an alphabet Σ) is a finite sequence of symbols from Σ e.g. xb3 is a string over Σ 2

ε is an empty string. The empty string is a string over any and every alphabet.

Definition: a Language (over an alphabet Σ) e.g. {1,0,11,00,1010101} is a language over the alphabet {0,1}

Remember mathematical notaion! Substrings too.

Next time Turing machines.

P.S. The textbook is your friend