# CS代考计算机代写 Glossary of notation for “Limits of Computation” module

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)}

AB 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