Week 1 Flashcards
What are sets
Collections of objects (usually homogenous) written {e1..en}
If x is an element of S, we write 𝑥 ∈ 𝑆. The set of elements of 𝑆 that have property 𝑃, may be written
{𝑥 ∈ 𝑆 | 𝑃(𝑥)}.
What is a total function
A total function 𝑓 : 𝐴 → 𝐵 always returns a defined value
What is a partial function
A partial function 𝑓 : 𝐴 → 𝐵⊥ returns a defined value, or ⊥ (bottom, non-determination)
What is a problem?
A uniform class of questions that has a clearly defined input parameter
Something with a definite and finite answer representing the solution
Solved by providing a function or deciding membership of a set.
What is a Turing machine?
Made up of an infinite tape, with marked-off squares capable of holding symbols from a finite alphabet. A sensing read-write head can travel along the tape, one square at a time.
How might a turing machine program be represented?
Transition function or state transition diagram.
Examples of imperative programming languages
Fortran, C, Pascal, Ada, Rust
What is the lambda calculus?
Formal system for expressing computation through abstraction and application using variable binding and substitution
What are constants in lambda calculus?
Constants are integers, characters booleans and operators and strictly speaking, are unnecessary. (e.g. +)
What are variables in lambda calculus?
A variable is a name e.g. (x)
What are applications of functions to an argument
Applications of functions to an argument are written by juxtaposition. Parenthesis disambiguate. (e.g. (fa))
What is a function in lambda calculus?
Described by lambda-abstraction. A lambda-abstraction binds a variable, if there is no lambda abstraction, then the variable is free.
What is the church turing thesis?
The church turing thesis is that the set of functions that are effectively computable are exactly the set computable by the lambda-calculus or the Turing machine.
What is a method? (copeland)
A method 𝑀 is set out in terms of a finite number of
exact instructions (each instruction being expressed by
means of a finite number of symbols);
∙ A method 𝑀 will, if carried out without error, always
produce the desired result in a finite number of steps;
A method 𝑀 can (in practice or in principle) be carried out
by a human being unaided by any machinery save paper
and pencil;
∙ A method 𝑀 demands no insight or ingenuity on the part
of the human being carrying it out.
