In Computability and Complexity we focus on languages because they give us an abstract way of describing a problem without getting bogged down with specifics.
Languages provide an abstract model of a computer that is independent of any technological implementation.
Computability is the study of computable problems. In other words it's the study of problems that have an algorithim.
Complexity is the classification of problems by their inherit difficulty.
A Universal Turing Machine is a Turing machine that is independent to any specific algorithim. In previous models each new algorithim required a new turing machine. Universal Turing Machine has the power to execute any algorithim provided it receives a desceription of the algorithim and the data the algorithim is to operate on.
A Universal Turing Machine Tu receives it's input as a string on a tape. The
form of the string is e(T)e(z) where e is an encoding function whose values
are strings in the {0,1}* set.
e(T)e(z) is accepted iff Tu accepts z
Context sensetive grammar is one where each production has the form wAx -> wYx, where w & x is a set of terminals and non-terminals and A & Y is a string of terminals. It means if you see A in the given context then you are permitted to replace it with Y.
Context free grammar on the other hand is a grammer where context is not important where each production has the form A -> Y, where A is a non-terminal and Y is a string of terminals and non-terminals.
Describe {(a^n)(b^n)(c^n) | n >= 1}
S = aBC | aBCT
T = ABC | ABCT
BA = AB
CA = AC
CB = BC
aA = aa
aB = ab
bB = bb
bC = bc
cC = cc
A machine that can recognise a context sensetive language other than a turing machine is the Linear Bounded Automaton. A Linear Bounded Automaton is a finite state machine with a finite length data store called a tape. Symbols can be read any position on this tape so the LBA has a read write head that can be moved Left or right by one cell each time. The machine can perform 3 actions based on a state/input combo: A = {Y,N,L,R}