Dennis Kroeb 11763388 ICS Deeltentamen 1 (2018) Gemaakt op: 21 feb 2019 Antwoorden zijn niet gegarandeerd goed. Excuus voor het door elkaar gebruiken van Engels/Nederlands, deal with it. ====== MODELLING AND SIMULATION ====== 1 First pillar: Experiment Second pillar: Theory 2 1: Test a real-world problem without actually doing it, which can save resources (time included) and is more safe. 2: Be able to test in an environment that would be hard to test under in the real-world (you have more control), which can make the experiment more accurate than real-world testing. 3: You can speed up time elapsed in the simulation, making it faster. (zie: https://en.wikipedia.org/wiki/Modeling_and_simulation#Interest_in_simulations) 3 1: "Don't fall in love with your model". If the model seems accurate in one scenario, it doesn't it is always applicable. 2: Be aware of the domain of the model/simulation, because for certain values the simulation might not be accurate anymore. 3: Be aware of factors not taken into account (a simulation is usually a simplified depiction of reality, and you might simplify things to much). 4 Validation: Checking whether the model is accurate Verification: Checking whether there are no mistakes in the model (bugs in the software) 5 A (Zie slides van eerste lecture dia 7 tot 12) B Continuous: Measuring earth's vibrations (earthquake detection) Discrete-Time: Displaying the number of cars built per month Discrete-Event: Displaying the state of a machine that changes, like a transmitter being idle, receiving, sending or sending and receiving at the same time. ====== FUNDAMENTALS OF CELLULAR AUTOMATA (CA) ====== 6 ? Class 1: An application where a homogeneous state is required Class 2: An application where stable or oscillating structures are required Class 3: An application where chaotic (pseudo-random) patterns are required Class 4: An application that is computationally universal or capable of simulating a turing machine 7 A: Moore's neighbourhood has r=1. {0, 1, 2} => k=3. Input alphabet: 3^(2 * 1 + 1) = 3^3 (= 27) (antwoord mag in exponenten geschreven worden) B: 27 states, k=3 => 3^27 (=7,625,597,484,987) (antwoord mag in exponenten geschreven worden) zie: https://www.wolframscience.com/nks/notes-3-2--numbers-of-cellular-automaton-rules/ C: 3^7 (=2187) totalistic rules. (tel het aantal transitions waar de som=N sum[0, 1, 2]=>3, sum[1,1,1]=>3, er zijn er 7 van de 27 die 3 geven) (k^(N*(k - 1) + 1) zie: http://mathworld.wolfram.com/TotalisticCellularAutomaton.html 8 A: 110 (base 2) B: t=1 00100 t=2 00100 (t=3 00100) C: L_trans: 0 (Observed above) L_cycle: 1 (Observed above) 9 A: Class 1: Homogeneous B: langton = (k^N-n)/k^N, n=6 (7 states produce 0), k=2, N=2 * r + 1, r=1 => K^3 = 8 (8-7)/8 = 1/8 (Bedenk dat 1 van de 8 staten non-quiescent, dus 1/8) C: reversible: NO (no unique predecessor for every state and configuration) totalistic: YES (??) probalistic: NO (??) additive: NO (http://mathworld.wolfram.com/AdditiveCellularAutomaton.html) symmetric: YES (because it's homogeneous?) ergodic: NO (because it's homogeneous???) ====== QUANTIFY COMPLEXITY ====== 10 1+k^N (bedenk {x/N | 0 >= x <= k^N}, dus 0 tot 1 heeft 1+k^N waarden) 11 56 [(0, 1, 0, 0, 0, 1, 0, 1), (0, 0, 1, 1, 0, 1, 0, 0), (0, 1, 1, 0, 0, 1, 0, 0), (0, 0, 1, 0, 0, 1, 0, 1), (0, 1, 1, 0, 1, 0, 0, 0), (0, 1, 0, 0, 1, 0, 0, 1), (0, 0, 0, 1, 0, 1, 0, 1), (1, 0, 0, 1, 0, 0, 0, 1), (0, 0, 1, 0, 1, 0, 0, 1), (0, 1, 0, 0, 0, 1, 1, 0), (1, 1, 1, 0, 0, 0, 0, 0), (1, 0, 1, 1, 0, 0, 0, 0), (1, 0, 0, 0, 1, 1, 0, 0), (0, 0, 1, 0, 0, 1 , 1, 0), (1, 0, 1, 0, 0, 0, 0, 1), (0, 0, 0, 1, 1, 0, 0, 1), (0, 1, 0, 0, 0, 0, 1, 1), (1, 1, 0, 1, 0, 0, 0, 0), (0, 1, 0, 0, 1, 0, 1, 0), (1, 1, 0, 0, 0, 0, 0, 1), (0, 0, 1, 0, 0, 0, 1, 1), (0, 0, 0, 1, 0, 1, 1, 0), (1, 0, 0, 1, 0, 0, 1, 0), (0, 0, 1, 0, 1, 0, 1, 0), (0, 0, 0, 1, 0, 0, 1, 1), (1, 0, 1, 0, 0, 0, 1, 0), (0, 0, 0, 1, 1, 0, 1, 0), (0, 1, 0, 1, 0, 0, 0, 1), (1, 1, 0, 0, 0, 0, 1, 0), (1, 0, 0, 1, 1, 0, 0, 0), (0, 0, 0, 0, 1, 1, 0, 1), (0, 1, 1, 1, 0, 0, 0, 0), (0, 0, 1, 1, 0, 0, 0, 1), (0, 1, 0, 0, 1, 1, 0, 0), (0, 1 , 1, 0, 0, 0, 0, 1), (1, 0, 1, 0, 1, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 0), (0, 0, 1, 0, 1, 1, 0, 0), (1, 0, 0, 0, 0, 1, 0, 1), (1, 1, 0, 0, 1, 0, 0, 0), (0, 1, 0, 1, 0, 0, 1, 0), ( 1, 0, 1, 0, 0, 1, 0, 0), (0, 0, 0, 1, 1, 1, 0, 0), (0, 0, 1, 1, 0, 0, 1, 0), (0, 0, 0, 0, 1, 1, 1, 0), (1, 0, 0, 0, 1, 0, 0, 1), (0, 1, 1, 0, 0, 0, 1, 0), (1, 1, 0, 0, 0, 1, 0, 0 ), (0, 0, 0, 0, 1, 0, 1, 1), (0, 1, 0, 1, 0, 1, 0, 0), (1, 0, 0, 0, 0, 1, 1, 0), (0, 1, 0, 1, 1, 0, 0, 0), (0, 0, 1, 1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 1, 1, 1), (1, 0, 0, 0, 0, 0, 1, 1), (1, 0, 0, 0, 1, 0, 1, 0)], length=56 12 https://ascrub.files.wordpress.com/2015/07/langton-1992-life-at-the-edge-of-chaos-figure-3.png?w=556&h=304 13 0101 continuously => 50% chance. => Hx = -(0.5 log2(0.5) + 0.5 log2(0.5)) = 1 14 max(-((x*log2(x)) + ((1-x)*log2(1-x))) = 1 met x=0.5 (intuition; trial and error; GRM; wolframalpha) 15 t = 1 [0, 0, 0, 0, 0, 0] [0, 0, 1, 1, 0, 0] [0, 0, 1, 1, 0, 0] [0, 0, 1, 1, 0, 0] [0, 0, 0, 0, 0, 0] t = 2 [0, 0, 0, 0, 0, 0] [0, 0, 1, 1, 0, 0] [0, 1, 1, 1, 1, 0] [0, 0, 1, 1, 0, 0] [0, 0, 0, 0, 0, 0] 16 GoL has: - Memory - AND & NOT gates (=> NAND gates) => any boolean function can be built - A UTM can run any other Turing Machine (note, all algorithms are turing machines) - GoL can run any algorithm => >>> GoL is a universal computer <<< 17 x NAND x = NOT x (x NAND y) NAND (x NAND y) = x AND y (voorbeeld, x=0, y=1 => !(!(0 && 1) && !(0 && 1)) = !(!(0) && !(0)) = !(1) = 0, en 0 && 1 = 0) 18 https://youtu.be/vGWGeund3eA?t=40 and https://www.rennard.org/alife/CollisionBasedRennard.pdf (page 8 and 9) ===== CA-BASED MODELS AND MEAN-FIELD APPROXIMATION ===== 19 ?? tba 20 ?? tba 21 ?? tba 22 ?? tba 23 ?? tba 24 ?? tba 25 ?? tba