Term
|
Definition
| (human-centric def: what passes between us when we communicate) the removal of uncertainty or suppression of randomness |
|
|
Term
|
Definition
| map associating symbols with what they represent- any isomorphism can encode any meaning, key is in construction/maintenance of map. this is the basis of coding. |
|
|
Term
|
Definition
| choice of symbol/physical representation for an idea; the need to invent new symbols or symbols that take time/space; hand #s, roman numerals grow in proportion to # |
|
|
Term
|
Definition
1) should not need to invent new symbols to encode new things
1a) should be a fixed alphabet
2) should be efficient- size doesn't grow with thing encoded- many things encoded in small space- length(d) about= its info content |
|
|
Term
|
Definition
| the # of combinations that can be made out of a set # of things. N symbols, code of length d, N^d combinations |
|
|
Term
|
Definition
| # of items that can be encoded explodes as length of code increases- efficient code |
|
|
Term
|
Definition
| combinatorial code that uses #s- (#, #) <#, #, #>. length of vector corresponds to dimension in space |
|
|
Term
| the more improbable an event.. |
|
Definition
| the more information provided when it occurs (claude shannon) |
|
|
Term
|
Definition
| identifies one object out of a set |
|
|
Term
| shannon's measurement of info content |
|
Definition
| how many y/n questions does it take to identify? pres approval has 7 questions, or 7 bits |
|
|
Term
| evolution defined through information theory |
|
Definition
| accumulation of useful information- to create an improbable event like the organization of atoms into an organism |
|
|
Term
| evolution defined through information theory |
|
Definition
| accumulation of useful information- to create an improbable event like the organization of atoms into an organism. not possible w/out some kind of info storage |
|
|
Term
|
Definition
| improbable event of weaving complex pattern into cloth- info not in loom, but punched cards-->1st computers |
|
|
Term
|
Definition
| encoding in some medium, transforming the encoding via rules. any time info transformed in precisely determined way, computation takes place |
|
|
Term
|
Definition
| the body is a machine, the mind is not separate from the body |
|
|
Term
|
Definition
| arithmetic can be performed by machine- invented one, based on pedometer |
|
|
Term
|
Definition
| logical reasoning can be performed by a machine (boolean arithmetic) |
|
|
Term
|
Definition
| babbage's analytical engine, born of difference engine- key was to separate sequence of operations from machines (create a program). store (storage) + mill (arithmetic) + program |
|
|
Term
|
Definition
|
|
Term
|
Definition
| 1) set out in finite terms exact instructions 2) produce desire result in finite steps 3) could be carried out by human and pencil 4) demands no insight/ingenuity on part of human |
|
|
Term
|
Definition
| any mechanically computable function can be completed on turing machine |
|
|
Term
|
Definition
| has a fixed set of states and can simulate any TM. reads the description of the encoded TM, acts like the encoded TM operating on the input |
|
|
Term
| what it means to be universal |
|
Definition
| means to store fixed set of symbols (tape, means to perform simple operations on those symbols (execution unit), means to follow precisely defined set of instructions |
|
|
Term
|
Definition
| has universality, can store a set of #s or symbols, perform operatiosn on them, and follow arbitrary set of instructions |
|
|
Term
|
Definition
| set of instructions that solves particular problem (a recipe) crucial elements: specified set of inputs, set of steps w/ clear beginning end, appropriately specific and feasible, eventually stops, must be executed by machine, work for all inputs. fastest algorithm is the best |
|
|
Term
| relationship bt size of text of a program and time it takes to run |
|
Definition
| there is no simple relationship |
|
|
Term
|
Definition
| expression describing # of steps needed as function of problem size |
|
|
Term
| # steps grows more slowly;faster;much faster;in proportion to input size |
|
Definition
| logarithmic;polynomial;exponential;linear complexity |
|
|
Term
| Travelling Salesperson Problem |
|
Definition
| there are n! paths, which makes complexity even worse than exponential. like the knapsack problem this is the best we've got. |
|
|
Term
|
Definition
| computationally unfeasible, currently. if we could solve one we could solve them all |
|
|
Term
| the self-reference of the halting problem |
|
Definition
| if P halts, B doesn't, if P doesn't, B does- if B doesn't, B does |
|
|
Term
| noncomputable problems reveal deep truths about computation |
|
Definition
| can be self-referential, can resist analysis |
|
|
Term
|
Definition
| continuous, infinite inputs, no separation from noise & entropy; finite, discrete set of inputs- put into binary, easy to identify noise |
|
|
Term
|
Definition
| the addition of error in copying info; the tendency for things to become disordered |
|
|
Term
|
Definition
| information pattern that is relatively permanent or common. digital copying allows stable information patterns |
|
|
Term
| one of the simplest forms of computing |
|
Definition
|
|
Term
| rules of the utm ecosystem |
|
Definition
| utms move randomly from tape to tape, can read or write more than one tape, fixed amount of tape, error sometimes occur |
|
|
Term
|
Definition
| write program R on a tape- a self-replicating program |
|
|
Term
|
Definition
| write x on each of two tapes (fecundity); write y on a tape, then check to make sure it was written correctly (copy-fidelity); if tape has z, re-write to refresh it (longevity) |
|
|
Term
| selfishness in UTM ecology |
|
Definition
| hoarding tapes, outcompeting neighbors for tapes |
|
|
Term
| separate copies of pattern are |
|
Definition
| indistinguishable- not the tape itself that matters, but the pattern on it |
|
|
Term
|
Definition
| machine that can only copy itself in the absence of mutations |
|
|
Term
|
Definition
| array of cels that have two states + simple set of rules for updating cell states over time. 2^8 (256) possible rule sets- 256 ways ca might evolve in time |
|
|
Term
| four classes of CA rule behavior |
|
Definition
| uniformity (all black/white/simple patterns); structure (nested patterns of considerable complexity); chaos (no predictable patterns); local structure (mixture of things happening locally with background simple patterns) |
|
|
Term
| fundamental fact of nature |
|
Definition
| simple computations can yield unexpected, surprising results |
|
|
Term
|
Definition
| pattern that emerges when molecules move randomly- can't observe by looking at one molecule |
|
|
Term
|
Definition
| nested- interesting bc contains itself- portion is rescaled version of whole thing |
|
|
Term
|
Definition
|
|
Term
| game of life as ex of emergence |
|
Definition
| existence of gliders/shooters shows properties not built in- high level properties can't be predicted from low-level ones |
|
|
Term
| emergence defines disciplinary boundaries |
|
Definition
| physics-> chem, chem->bio, bio->anthro, antro->philosophy/lit/art |
|
|
Term
| emergence's relationship to noncomputability |
|
Definition
| cannot tell by looking at rules whether interesting properties will emerge. also the only way to find out for all programs p "does p do x" is to run program p. computation is inscrutable! |
|
|
Term
|
Definition
| what underlies the wave/particle level of physics? the universe is a computer |
|
|
Term
| key to emergence of life on earth |
|
Definition
| discovery by nature of how to extract and efficiently encode information- had only atoms/molecules to work with |
|
|
Term
| life= metabolism;reproduction |
|
Definition
| obtaining energy from environment to break dwon raw materials into building blocks and construct/repair body & structure; make approximate copies of one's self |
|
|
Term
|
Definition
| constructive, copying and control machines creates self-replicating machine+blueprint. gets corrupted and carries corruption |
|
|
Term
|
Definition
| collisions of molecules, leading to rearrangement of atoms into new molecules- depends on molecule shape |
|
|
Term
|
Definition
| molecule whose presence accelerates reaction without being changed |
|
|
Term
|
Definition
| molecule made by stringing many small units from fixed set. long chains, define molecules shape and can carry info. sugar, amino acid, nucleotide- 3 polymers imp in life |
|
|
Term
|
Definition
| how self-replicating info could arise. molecule that catalyzes own reaction. was probably rna |
|
|
Term
|
Definition
| consist of backbone+base, always read 5->3, bases can bond to each other (A to U or G to C) |
|
|
Term
|
Definition
| AUGC- elaborate structure, carry info, self-replication possible |
|
|
Term
| rna templated polymerization |
|
Definition
| catalyst that causes copying of any other rna molecule- a tape copying turing machine |
|
|
Term
|
Definition
| interacts w/ environment, resists entropy |
|
|
Term
|
Definition
| evidence for rna world in prebiotic world- put methane, ammonia, hydrogen, water + electric current, found organic compounds |
|
|
Term
|
Definition
| Catalytic and autocatalytic RNA can be produced in lab, Key cellular reactions are still catalyzed by RNA in nature, Even simpler replicators could have predated RNA |
|
|
Term
|
Definition
| collection of molec that together are capable of more efficient replication- ex ribozymes that catalyze nucleotide production- beginnings of the cell |
|
|
Term
|
Definition
| no machine needed, as in membranes |
|
|
Term
|
Definition
| polymers with 20 possible subunits- much greater variety of molecule shapes available with their existence |
|
|
Term
|
Definition
| improves longevity, much more stable, thymine instead of cytosine allows error correction |
|
|
Term
|
Definition
| bacteria, archaea, eucaryotes- different ribosome, energy production different |
|
|
Term
| information processing machinery |
|
Definition
| bacteria (unshielded chromosomes) and archaea & eucaryotes (histones, promoters) |
|
|
Term
| alternate definitions of life |
|
Definition
| nasa- information first: self-sustained chemical capable of darwinian evolution. sagan- metabolism first: localized region increases in order through cycles driven by energy flow |
|
|
Term
|
Definition
| first protein we learned a lot about- transports oxygen in lower animals (we use hemoglobin) |
|
|
Term
|
Definition
| digestion. digests whatever contacts- deactivated while in cell until stomach |
|
|
Term
| myosin and actin, bathed in ATP |
|
Definition
| myosin flexes- millions of molecules together make a muscle fiber |
|
|
Term
|
Definition
| doesn't repeat- high information content. as in, chromosomes |
|
|
Term
|
Definition
| eukaryotes->prokaryotes->viruses->proteins->small molecules->atoms |
|
|
Term
|
Definition
| defense. several flexible arms-adaptive. 2 to 10 binding sites, 10^15 in our blood |
|
|
Term
|
Definition
| communication. describes amount of sugar in blood, tells organs what to do. small distinctive shape, difficult folding problem |
|
|
Term
|
Definition
| structure- triple helix. tendons, skin, organs |
|
|
Term
|
Definition
| protein folding is a problem for cells- misfolding->alzheimers, sickle cell disease. folding environments chaperone folding |
|
|
Term
|
Definition
| darwin said inherited traits are fluid, children get mixtures. mendel said at least some are discrete- traits inherited in numerical ratios, each parent passes half. genetic info is digital. |
|
|
Term
|
Definition
| shows pneumonia's virulence changed by altering dna- implicates dna as material of heredity |
|
|
Term
| dna replication is obvious |
|
Definition
| because of the structure- two strands with paired bases |
|
|
Term
|
Definition
| part of dna where unzipping starts |
|
|
Term
|
Definition
| shows where replication should start from by creating tags |
|
|
Term
|
Definition
| protein structure of dna inherited in egg cell |
|
|
Term
|
Definition
| dna transcribed to rna, rna translated to proteins (takes place in ribosome outside nucleus) |
|
|
Term
|
Definition
| code for a single protein. many genes on each dna strand. specific markers show start/stop of genes |
|
|
Term
|
Definition
| code embodied in tRNA. amino acid on one end, anticodon on other. 20 kinds, one for each amino acid |
|
|
Term
|
Definition
| two parts lock together with mRNA in between. decoding happens here |
|
|
Term
|
Definition
| remarkable separation of information and machinery |
|
|
Term
|
Definition
| responsible for info flow. finds mRNA, matches codons with anticodons. |
|
|
Term
| error resistance of gene encoding |
|
Definition
| many more codes than amino acids |
|
|
Term
|
Definition
| process of making two things similar. allows single evolutionary advance to be used over and over. transformation of repeating structures can be basis for emergence of new species. |
|
|
Term
|
Definition
| how embryo forms. timing and place of gene expression is a control problem |
|
|
Term
|
Definition
| start at first instruction, proceed in order unless instructed otherwise. tedium fixed with subroutines |
|
|
Term
|
Definition
| instruction that presumes certain level of knowledge-packaged set of instructions that can be used in mult. programs/places/times |
|
|
Term
|
Definition
| gene where "run subroutine" command is found. every multicellular animal has this 180 base pair sequence in common. part of transcription factor |
|
|
Term
|
Definition
| tells homeotic genes whether to turn other genes on |
|
|
Term
|
Definition
| a repressor, as with fluorescence of squid |
|
|
