cognitive science - computation, Turing machines, computability

when was the difference engine created?

1822

why was the difference engine created?

the British navy needed tables of polynomial tables and humans often made mistakes when computing these

what algorithm did the difference engine use?

the method of divided differences

when was the analytical engine created?

1837

who invented the analytical engine?

Charles Babbage

what was the analytical engine designed to be?

a mechanical device capable of calculating any mathematical function, a general purpose computer

what did the analytical engine’s architecture consist of?

a store, mill, and punched cards

what was the analytical engine’s store?

a memory where numbers and intermediate computations are held

what was the analytical engine’s mill?

a central processing unit that performs computations using pegs and rotating barrels

what were the punched cards used for in the analytical engine?

program control

what were the two kinds of punched cards the analytical engine used?

variable and operational cards

what did the analytical engine use the variable cards for?

inputting data

what did the analytical engine use the operational cards for?

transferring numbers between the store and the mill

when was the first program written?

1843

who wrote the first program?

Ada Lovelace

what was the first program?

a set of instructions for the analytical engine to compute Bernoulli’s Number

what did the first program lead people to postulate?

that a general-purpose computer could do anything given the right data/input and instructions/software

what was Turing’s On Computable Numbers?

a formal theory/model of computation now known as a Turing machine

what did the Turing machine demonstrate?

the possibility of performing any computational calculation through rules and data storage

what is a Turing machine?

an idealized, mathematical abstraction of a computer

what does a Turing machine consist of?

a 1D tape of cells of unlimited length with a symbol from a finite alphabet written on each cell, a read/write head that looks at one cell at a time, and a control program

what is the first step of any computation on a Turing machine?

writing symbols in the squares of the paper tape

what do you look at on a Turing machine at each step of computation?

only the symbol written in exactly one of the squares

what does each action depend on while computing on a Turing machine?

the symbol being viewed and the state of the read/write head

what does each action on a Turing machine consist of?

writing a symbol on the square at hand and then shifting attention to the square to the left or right

what can the read/write head of a Turing machine do?

move left or right on the tape, replace 0 with 1, 1 with 0, or leave a symbol unchanged

what is a control program for a Turing machine?

a program that specifies the machine’s action in each possible state when confronted with each possible symbol

what actions might be specified by a Turing machine’s control program?

a change of symbol on the square at hand, a movement one square to the left or right, or a change of state

what is the Marrian analysis of a Turing machine at the computational level?

characterization of the multiplication function

what is the Marrian analysis of a Turing machine at the algorithmic level?

0s and 1s, L and R actions, the control program

what is the Marrian analysis of a Turing machine at the implementation level?

physical construction of a Turing machine

for the purpose of computation, does it matter how a Turing machine is constructed or what it’s made of?

no

for the purpose of computation, does it matter that a Turing machine has the capability of assuming different states and acting accordingly in each?

yes

what parts of modern computers can be traced back to Turing machines?

programs are evolved control/action tables, CPU is an evolved read/write head unit, and hard drive is an evolved tape

what makes a function Turing-compatible?

if it can be implemented on a Turing machine

what can a Universal Turing Machine do?

for any Turing-computable procedure, it can simulate any other machine that executes it

what did Turing propose?

mental activity is computation

what is the halting problem?

it is impossible to write a program that determines whether another program will halt

what is the time complexity of a Turing machine?

how much more time the program needs to complete when you increase the size of the size of the input

what does it mean if an algorithm runs in polynomial time?

the number of steps required to compute can be expressed as a polynomial of the input length n

what is the time complexity class of algorithms called?

P

when is a function (usually) computable?

when its solution can be found in polynomial time

what does it mean that polynomial algorithms scale well?

small changes to the size of the input do not typically induce enormous changes to the overall runtime

what is an NP-hard problem?

a problem in which the time required to solve grows exponentially as the problem size grows bc its time complexity can’t be expressed as a polynomial

what does NP-hard mean?

nondeterministic polynomial time

what is an example of an NP-hard problem?

traveling salesman problem