Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Abstract Machines (bephpug)

Igor Wiedler
February 04, 2014

Abstract Machines (bephpug)

Igor Wiedler

February 04, 2014
Tweet

More Decks by Igor Wiedler

Other Decks in Programming

Transcript

  1. • Link between our universe and computational universe • Cellular

    automata are self-replicating abstract machines • Humans are self-replicating biological machines (down to the cellular level) • Or is the entire universe a single machine?
  2. • if alive • 2 or 3 neighbours to survive

    • if dead • exactly 3 neighbours to spawn • else • cell is dead
  3. 1 1 2 1 3 5 2 2 1 2

    2 2 2 3 2 1
  4. 1 1 2 1 3 5 2 2 1 2

    2 2 2 3 2 1
  5. • Other cellular automata • Codd’s automaton (8 states) •

    Langton’s loops (8 states) • Wireworld (4 states)
  6. 234

  7. 34

  8. 4

  9. • M = (Q, Σ, δ, q0, F) • Rule

    δ = (qi, a → qi1) • Can accept regular languages
  10. $rules = [ 0 => ['c' => 1, 'f' =>

    7, 'r' => 9], 1 => ['l' => 2], 2 => ['o' => 3], ... ]; ! $tokens = ['f', 'i', 'x', 'e', 's', ' ', '#', '1', '2', '3', '4', 'EOF']; ! foreach ($tokens as $token) { if (!isset($rules[$state][$token])) { throw new NoTransitionException(); } ! $state = $rules[$state][$token]; } ! $accepted = in_array($state, $accept_states);
  11. baz

  12. baz

  13. az

  14. z

  15. • Does not add computational power • Can be compiled

    to a DFA • Previous DFA example already showed this • Basic quantum physics
  16. e

  17. e

  18. • M = (Q, Σ, Γ, δ, q0, Zo, F)

    • Rule δ = (qi, a, sj → qi1, sj1) • Can accept context-free languages
  19. • M = (Q, Σ, Γ, δ, q0, b, F)

    • Rule δ = (qi, aj → qi1, aj1, dk) • Can accept recursively enumerable languages • Or loop forever
  20. while (!in_array($state, $accept_states)) { $read_val = isset($tape[$position]) ? $tape[$position] :

    '_'; ! if (!isset($rules[$state][$read_val])) { throw new NoTransitionException(); } ! list($write_val, $move_dir, $new_state) = $rules[$state][$read_val]; ! $tape[$position] = $write_val; ! if ('l' === $move_dir) { $position--; if ($position < 0) { $position++; array_unshift($tape, '_'); } } else if ('r' === $move_dir) { $position++; if ($position >= count($tape)) { array_push($tape, '_'); } } ! $state = $new_state; }
  21. U M

  22. • System capable of emulating a turing machine • Unbounded

    storage • Conditional branching • Recursion
  23. • If PHP can only do as much as a

    turing machine, why bother? • Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy. • Epigrams on Programming by Alan Perlis
  24. • Is our universe really turing complete? • Or are

    the possible paths finite and pre- determined? • Do even stronger forces exist?
  25. <?php $data = <<<'DATA' $program = <<<PROGRAM <?php \$data =

    <<<'DATA'\n$data\nDATA; $data ! PROGRAM; echo $program; DATA; $program = <<<PROGRAM <?php \$data = <<<'DATA'\n$data\nDATA; $data ! PROGRAM; echo $program;
  26. • Let R be the set of all sets that

    do not contain themselves • Does R contain itself? • If yes, then R’s definition is incorrect • If no, R is not in the set, so it must contain itself
  27. • Liar paradox: “This sentence is false.” • Type theory

    • Hierarchy of types avoids self-reference
  28. • David Hilbert asks for an algorithm that decides if

    a statement in first-order logic is universally valid • Halting problem can be reduced to Entscheidungsproblem • Machine that determines if another machine will halt