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