Algorithms & Computation

week 1 + week 2 computation lecture

What is an algorithm?

a set of instructions for any input that gives a way to compute the correct output

What is computation?

the physical implementation of an algorithm

What is the babylonian algorithm?

Finding a perfect square

What is the babylonian method?

What is the pseudocode for the babylonian algorithm?

What happens in each iteration of the loop in the babylonian algorithm?

we’re cutting the maximum possible distance to the solution in half

What are the 2 problems with the babylonian algorithm?

• the algortihm can fail due to roudning errors

• (may) only work for perfect squares

What is all data stored on computers stored in?

bits (0 or 1)

What is an ordered set of 8 bits?

a byte

What was the famous decision problem Hilbert formylate in 1928?

Does there exist an algorithm that takes as input any mathematical statement (in first order logic) and gives as output whether the statement is true or false

Who were the 2 mathematicians that solved the decision problem independently and what did they do to solve it?

• Church - developed new branch of mathematics λ-calculus

• Turing - Turing machine

What is a turing machine?

• infinite tape divided into cells - each cell 0/1

• tape head - move up & down tape + read symbol directly underneath

• machine has fixed internal memory (finite set of possible internal states)

• at each state the machine will:

  • overwrite current symbol w/ diff symbol

  • change internal state

  • move one step left/right

  • halt

What is the input and the output for a turing machine?

• INPUT - initially whole tape = blank, except for finite string of 0s & 1s starting directly underneath the head extending right

• OUTPUT - once TM halts, symbol directly beneath the head

What is the halting problem?

• there is no Turing machine that is guarenteed to halt for all possible input

  • problem is undecidable/uncomputable

• therefore the halting problem is uncomputable

What are the repercussions of the halting problem?

• in programming - there is no way to verify whether that program ever terminates

• in computer science - there are some problems that cannot be computed

• in maths - there are mathematical truths that cannot be proven

• in physics - some processes that can never occur in the universe (naturally or otherwise)