FB Flashcards
Function unknown to be computable
Patterns of the digits of pi - function is not known to be effectively computable or non-computable
∅
stands for the empty set which has no
members. The empty set may also be written {}.
Set membership
x ∈ S
subset
S is a subset of T, written S ⊆ T, exactly when for every
x ∈ S it also holds that x ∈ T.
Set union, set intersection, set difference
Set union is written as S ∪ T, set intersection is written as
S ∩ T, and set difference is written as S \ T
set product
notation S × T
stands for the set of all ordered pairs (x, y) such that x ∈ S
and y ∈ T.
N
2
set of all pairs of natural numbers
N
set of all natural numbers: 0, 1, 2, 3, and so on.
Z
set of all integers: . . . , −3, −2, −1, 0, 1, 2, 3, . . . .
Q
set of all rational numbers, each of which is the result
of dividing an integer x by a positive integer y, written x/y
R
set of all real numbers, each of which can be viewed
as the sum of an infinite sequence of rational numbers.
binary relation
a set of ordered pairs.
application
Given a binary relation R, the application R(x) denotes y
such that (x, y) ∈ R, if there is exactly one such y, and is
otherwise undefined.
domain
dom(R) = { x ∃y. (x, y) ∈ R }.
range
ran(R) = { y ∃x. (x, y) ∈ R }.
Function Space
S to set T, written S → T, is the
set of every function f such that dom(f ) ⊆ S and ran(f ) ⊆ T.
If f ∈ S → T, it is said that f is a function from S to T.
Total function spaces
A function f is total on S if and only if dom(f ) = S. The
total function space from S to T, written S −
tot → T, is the set
of every function f ∈ S → T such that dom(f ) = S.
inverse
the inverse of a binary relation R is
R−1 = { p ∃x. ∃y. p = (y, x) and (x, y) ∈ R }.
one-to-one (injective)
exactly when
both R and its inverse R
−1
are functions.
onto S (surjective to S)
A function f is onto S (surjective to S) if and only if
ran(f ) = S.
bijection
A bijection from S to T is a function that is total on S,
one-to-one (injective), and onto T (surjective).
enumerate
To enumerate a set is to arrange its members in a single list
with a first entry, a second entry, etc., so that:
- every member of the set appears sooner or later in the list and
- every entry in the list belongs to the set. In an enumerated set, every member of the set must be listed
after at most a finite number of other members.
cardinality
Sets can be finite or infinite. The notation |A| stands for the
cardinality of A, i.e., the number of members in the set A.
countable set
When thinking more about a set’s size rather than about
listing the set, we say an enumerable set is countable.
countably
infinite
lf a set is enumerable and infinite, we say it is countably
infinite (or enumerably infinite)
a
The size of a countably infinite set is a.
N countable?
The set N is countably infinite.
|A| = |B|
(i.e., A and B are of the same size) if and only if
there exists a bijection f from A to B.
Uncountability
[0, 1[ is not countable.
enumeration function
A set with an enumeration function is enumerable and also
countable.
Uncountability of the power set of N
t ℘(N) is not countable.
Uncountability of P(N)
Proof by contradiction.
Assume P(N) is countable. Meaning we can list all elements in a sequence.
Since S contains all possible subsets of N, we can represent each element of S as a sequence of 0s and 1s, where the ith position of the sequence is 1 if the ith element of N is included in the subset, and 0 otherwise.
Now, let’s construct a new subset of N, T: for each ith element of N, we include it in T if the ith position of the sequence corresponding to the ith element in S is 0, and we exclude it from T if the ith position of the sequence is 1. In other words, we construct T by flipping the membership status of each element of N in each corresponding subset of S.
It can be shown that T is not in S, since T differs from every subset of S in at least one element. Therefore, we have found a subset of N that is not in the sequence S, contradicting the assumption that S contains all possible subsets of N. Hence, we conclude that the power set of N is uncountable.
Q states TMB for n-1
q0: go right til ^
q1: go through left through 0s til 1. Swap 1 with 0, R.
if ^ Halt.
q2: go right through 0 swap with 1. When ^ L.
q3: go left through 0+1, ^ go R.
q4: 1 Halt. If 0, go through right ^.
If ^ go L.
q5: replace ^ with 0. Halt
q6: Halt
Define Effective Procedure:
An effective procedure is one that always correctly returns the right answer, only where there is a finite number of steps which are mechanical if all requested resources are provided.
Effectively computable
A process is effectively computable exactly when an effective procedure calculates it.
Church Thesis - TM
Every effectively computable function is Turing computable
Solvable?
Halt?
Even?
Halt - unsolvable. No TM calculates halt.
Even is solvable
Surjective (onto)
Every B has some A
Injective (one-to-one)
B can’t have many A
Bijective (surjective, injective)
A to B, perfectly
Turing Computable
A function f ∈ N^j → N^k is Turing Computable exactly when there exists a Turing Machine M such that f = unaryIOj(M). f is computed by M
f (x) = x + 1 for every x ∈ N
f = unaryIO1,1(Madd1)
