Glossary of notation for “Limits of Computation” module
© Billiejoe Charlton and Bernhard Reus 2009-17
Symbol
Sets and functions:
{−}
{− | −}
N D ∪
A(x) x∈S
⊆
×
\
∈ ∋
→
Name
set brackets
set comprehension
natural numbers set of binary trees union
indexed union
subset
proper subset
Cartesian product
set difference
set membership set membership
Description
E.g. {a, b, c} is the set containing three elements a, b and c {x | P (x)} is the set of objects x having property P (x)
E.g. {x | x ∈ N and x > 3} = {4, 5, 6, . . .} The set of the natural numbers 0,1,2,3,…
The set of binary trees built from nil and (− . −)
A∪B is the set of all elements in either A or B or both
E.g. {1,2,3} ∪ {2,5} = {1,2,3,5} Means the union of A(x) for all xs in S
E.g. Ax meansA1∪A2∪A3 x∈{1,2,3}
A ⊆ B means every element of A is also in B E.g. {1} ⊆ {1,2} but not {1,2} ⊆ {1}
A B means that B contains all the elements of A and some more elements; A and B cannot be equal
A×B is the set of pairs of one element from A and one from B E.g. {0,1} × {a,b} = {(0,a),(0,b),(1,a),(1,b)}
A\B is the set of elements from A which are not in B E.g. {0, 1, 2}\{1, 3} = {0, 2}
x ∈ A means x is in (is an element of) the set A A ∋ x means x is an element of set A
(this is just x ∈ A written in a different order) A → B denotes the set of functions from A to B
f : A → B means that f is a function from A to B
1
Symbol
Sets and functions (continued):
⊥
−⊥
f(a)↓ f(a)↑ L-programs L-data L-store fn(x)
λx. −
Symbol
Programming:
=⇒
[d1, d2, ··· , dn] ⟨d1 . d2⟩
nil n
Name
bottom
Description
f(x) = ⊥ means that (partial) function f is undefined at x In particular, ⊥ represents non-termination of programs
X⊥ is the set X plus ⊥ as an additional element Hencef:A→B⊥ meansfisapartialfunctionfromAtoB
Means that partial function f is defined at a (same as f(a) ̸= ⊥)
Means that partial function f is not defined at a (same as f(a) = ⊥)
The set of programs written in language L
The set of data values used by programs written in language L
The set of stores used when giving the semantics of language L
Function f applied n times to x, e.g. f3(x) is f(f(f(x)))
λx.f(x) means the function which maps x to f(x)
E.g. written this way, the squaring function is λx. x × x
lambda abstraction
Name
list notation
Description
Used for rewrite rules (not available in WHILE)
A list of length n, with first element d1, second element d2 etc.
A binary tree with left subtree d1 and right subtree d2 In WHILE, one uses the cons operator: cons d1 d2
A right-spined binary tree containing n + 1 nils; encodes number n. E.g. nil 3 = (nil.(nil.(nil.nil)))
2
Symbol
Semantics: {Xi : di }
Name
store
store update
semantics of language L
semantics of program p
For WHILE language:
For machine models:
Description
E.g. {X : nil, Y : (nil.nil)} means a store in which variable X contains value nil and variable Y contains value (nil.nil)
Means a store that’s the same as σ, except that variable X has the value V The semantics (meaning) of a programming language L, which is a
function L-programs → (L-data → L-data⊥)
The meaning of a particular program p (written in language L) as a
function from input to output, i.e. a function L-data → L-data⊥ The value of a WHILE expression E in store σ
Command C terminates when run in store σ, with resulting store σ′
Program (or machine) p transits from state s to state s′ in a single step Program (or machine) p transits from state s to state s′ in 0, 1 or more steps
Turing Machines (with tapes and heads etc.)
Goto language (“flowchart language”); has a “goto” statement instead of the “while” loop statement
Successor Random Access Machines; has arbitrarily many registers holding natural numbers; allows indirect addressing
Counter Machines: much simpler than SRAM; machines contain a limited number of counters
Counter Machines with only 2 counters
σ[X := V ] L
− L
p
E Eσ
C ⊢ σ → σ′
p ⊢ s → s′ p ⊢ s →∗ s′
Computation models:
TM GOTO
SRAM
CM
2CM
3
Symbol
Complexity symbols: timeLp(d)
T
C ⊢time σ ⇒ t
L ≼ptime M
L ≼lintime M
L ≼lintime-pg-ind M L ≡ptime M
L ≡lintime M
L ≡lintime-pg-ind M Ltime(f (n))
Lptime
Llintime
TIMEL(f) PL
EXPL
LINL
NPL
Name
running time
Description
The time taken for a program p ∈ L-programs to run on input d
T E is the time taken to evaluate WHILE expression E
WHILE command C terminates after t time steps, when run in store σ′ Language M can simulate language L up to a polynomial difference in time Language M can simulate language L up to a linear difference in time
M can simulate L up to a program-independent linear difference in time Languages L and M are polynomially equivalent
Languages L and M are linearly equivalent
Languages L and M are strongly linearly equivalent
The set of L-programs with time bound f (where f : N → N)
The set of L-programs bounded by some polynomial function
The set of L-programs bounded by some linear function
The set of decision problems (not programs!) that the language L can decide in time f
The set of decision problems (not programs) that the language L can decide in polynomial time
The set of decision problems (not programs) that the language L can decide in exponential time
The set of decision problems (not programs) that the language L can decide in linear time
The set of decision problems accepted by a nondeterministic L-program in polynomial time
4
Symbol
Other symbols:
∀
iff
≃
⊑
|x| X
.
n − m X∗
ε
Name
Description
“for all”
“if and only if”
x ≃ y means either x and y are both undefined, or both are defined and they are equal
S ⊑ T means: any program in language S is also a program in language T , and has the same semantics
Denotes the size of an object (e.g. binary tree) x The encoding or translation of some object X
(see e.g. rules for encoding numbers or programs as binary trees) Gives n−m if n > m and 0 otherwise
Strings built from 0 or more repetitions of the string expression X as used in regular expressions; e.g. {0, 1}∗ denotes binary strings
ε is the empty string, i.e. the string of length 0
language matching
size
cutoff subtraction Kleene star
empty string
5