Understanding Computation (60 page)

Read Understanding Computation Online

Authors: Tom Stuart

Tags: #COMPUTERS / Programming / General

BOOK: Understanding Computation

4.03Mb size Format: txt, pdf, ePub

Read Book Download Book

quine, Programs Can Refer to Themselves
quotation marks, String Interpolation

Range class, Enumerable

range of values, Data Structures

recursive code

avoiding arbitrary recursion, Avoiding arbitrary recursion – Avoiding arbitrary recursion
infinite loops, Numeric Operations
partial recursive functions, Partial Recursive Functions – Partial Recursive Functions
stack overflow, Statements

reduction contexts, Applications

reduction relation, Small-Step Semantics

reduction semantics, Applications

reductions, small-step

about, Small-Step Semantics
applications, Applications
expressions, Expressions – Expressions
statements, Statements – Statements

Regexp class, Just Add Power

regular expressions

about, Regular Expressions
concatenating, Semantics
converting NFA to, Just Add Power
nested strings and, Just Add Power
parsing, Parsing – Parsing
semantics, Semantics – Semantics
syntax, Syntax – Syntax

regular languages, Nondeterminism

relational semantics (see big-step semantics)

remove_constant message, Removing Constants

Rendell, Paul, Conway’s Game of Life

Rice’s theorem

about, Other Undecidable Problems
abstract interpretation and, Safety and Approximation: Adding Signs , Applications
implications of, Depressing Implications
predicting program behavior, Programming in Toyland

Ruby programming language

blocks of code, Blocks
classes and modules, Classes and Modules
control flow, Control Flow
defining constants, Defining Constants
Enumerable module, Enumerable
inspecting objects, Inspecting Objects
Interactive Ruby Shell, Interactive Ruby Shell
local variables and assignment, Local Variables and Assignment
monkey patching, Monkey Patching
objects and methods, Objects and Methods
printing strings, Printing Strings
specification by implementation, The Meaning of “Meaning”
string interpolation, String Interpolation
Struct class, Struct
value types supported, Values – Procs
variadic methods, Variadic Methods

rule 110, Rule 110

rulebooks

cyclic tag system and, Cyclic Tag Systems
deterministic finite automata, Simulation
deterministic pushdown automata, Simulation
deterministic Turing machines, Simulation
nondeterministic finite automata, Nondeterminism
Turing machines, Subroutines , General-Purpose Machines

rules

deterministic finite automata, States, Rules, and Input
deterministic pushdown automaton, Rules
deterministic Turing machines, Rules
nondeterministic finite automata, Nondeterminism
rulebooks and, Simulation

s-expressions, Code Is Data

Sagan, Carl, Programming with Nothing

Scheme programming language, Applications

self-referential programs, Programs Can Refer to Themselves – Programs Can Refer to Themselves , Why Does This Happen?

semantics

about, The Meaning of “Meaning”
axiomatic, Alternatives
comparing styles, Statements
denotational, Denotational Semantics – Applications
dynamic, Correctness , Static Semantics
formal, The Meaning of “Meaning” , Formal Semantics in Practice – Alternatives
lambda calculus, Semantics – Reducing expressions
operational, Operational Semantics – Applications , Expressions , Statements
reduction, Applications
regular expressions, Semantics – Semantics
static, Correctness , Static Semantics – Benefits and Limitations

sequence statements

big-step semantics, Statements
small-step semantics, Statements

Set class

#& method, Nondeterminism
#+ method, Nondeterminism
about, Nondeterminism
#subset? method, Nondeterminism

Simple programming language example

about, Small-Step Semantics , Programming with Nothing
big-step semantics, Big-Step Semantics – Applications
denotational semantics, Denotational Semantics – Applications
implementing parsers, Implementing Parsers – Implementing Parsers
small-step semantics, Small-Step Semantics – Applications

simulation

deterministic finite automata, Simulation
deterministic pushdown automaton, Simulation – Simulation
general-purpose machines, Simulation
nondeterministic finite automata, Nondeterminism
nondeterministic pushdown automaton, Simulation – Simulation
Turing machines, Simulation
universal Turing machines, Simulation

SKI combinator calculus, SKI Combinator Calculus – Iota

small-step semantics

about, Small-Step Semantics
applications, Applications
comparing styles, Statements
correctness, Correctness
expressions, Expressions – Expressions
statements, Statements – Statements

Smalltalk programming language, Objects and Methods

Smith, Alex, Wolfram’s 2,3 Turing Machine

square brackets [ ], Data Structures , Procs

stack overflow, Statements

start state, States, Rules, and Input , Nondeterminism

statements

about, Statements
assignment, Statements
big-step semantics, Statements – Statements
conditional, Statements , Booleans – Booleans
denotational semantics, Statements – Statements
do-nothing, Statements
sequence, Statements , Statements
small-step semantics, Statements – Statements

states

accept, Output , Nondeterminism , Semantics
balanced brackets example, Just Add Power
deterministic finite automata, States, Rules, and Input
Game of Life and, Conway’s Game of Life
implementing, Semantics
nondeterministic finite automata, Nondeterminism , Semantics
start, States, Rules, and Input , Nondeterminism
Turing machines, Internal Storage

static semantics

about, Correctness , Static Semantics
benefits and limitations, Benefits and Limitations – Benefits and Limitations
implementing, Implementation – Implementation

storage

deterministic finite automata, Output
deterministic pushdown automaton, Storage
deterministic Turing machines, Storage – Storage
multidimensional tape, Multidimensional Tape
multiple tapes, Multiple Tapes
nondeterministic finite automata, Nondeterminism
Turing machines, Internal Storage – Internal Storage

streams

infinite, Infinite streams – Infinite streams
native Ruby, Infinite streams

strings

concatenating, Expressions , Syntax
FizzBuzz example, Strings
interpolating, String Interpolation
nested, Just Add Power
printing, Printing Strings

Struct class

about, Struct
#inspect method, Expressions
new method, Struct
#to_s method, Expressions

structural operational semantics (see small-step semantics)

subroutines, Subroutines

super keyword, Classes and Modules

superclasses, Classes and Modules

symbols

about, Basic Data , Free Moves
hashes and, Data Structures
key-value pairs and, Data Structures
SKI combinator calculus and, SKI Combinator Calculus – Iota

syntactic analysis

about, Parsing with Pushdown Automata
parsing with PDA, Syntactic Analysis – Syntactic Analysis

syntax

about, The Meaning of “Meaning” , Syntax
lambda calculus, Syntax – Syntax
parsers and, Syntax
procs, Syntax
programs and, Syntax
regular expressions, Syntax – Syntax

tag systems

about, Tag Systems – Tag Systems
cyclic, Cyclic Tag Systems – Cyclic Tag Systems

tail call optimisation, Statements

tape storage

multidimensional tape, Multidimensional Tape
multiple tapes, Multiple Tapes

TM (Turing machines), Encoding

(see also UTM)
about, Programming with Nothing
decidability, Decidability – Decidability
deterministic, Deterministic Turing Machines – Simulation
deterministic finite automata and, General-Purpose Machines
encoding, Encoding
external memory and, Deterministic Turing Machines
Game of Life, Conway’s Game of Life – Conway’s Game of Life
halting problem, The Halting Problem – Fundamentally impossible
lambda calculus and, Lambda Calculus – Lambda Calculus
maximum power, Maximum Power – Multidimensional Tape
multidimensional tape, Multidimensional Tape
multiple tapes, Multiple Tapes
nondeterministic, Nondeterministic Turing Machines
partial recursive functions and, Partial Recursive Functions – Partial Recursive Functions
programs standing in for, Programs Can Stand In for Turing Machines
rule 110, Rule 110
simulation, Simulation
SKI combinator calculus and, SKI Combinator Calculus – Iota
storage, Internal Storage – Internal Storage
subroutines, Subroutines
tag systems and, Tag Systems – Cyclic Tag Systems
Wolfram’s 2,3 Turing machine, Wolfram’s 2,3 Turing Machine

total programming languages, Universal Systems Can Loop Forever , Depressing Implications

transition functions, Free Moves

transition semantics (see small-step semantics)

transitions, Free Moves

Treetop language, Implementing Parsers , Parsing – Parsing

Turing machines (see TM)

Turing, Alan, The Ultimate Machine , Storage , Rules

Turner, David, Depressing Implications

unary representation, Encoding

undecidable problems

about, Decidability
halting problem, The Halting Problem – Fundamentally impossible
implications of, Depressing Implications – Depressing Implications
toy example, Other Undecidable Problems – Other Undecidable Problems

universal Turing machines (see UTM)

unreachable code, Coping with Uncomputability

untyped lambda calculus (see lambda calculus)

UTM (universal Turing machines)

about, General-Purpose Machines , Universality Is Everywhere
code is data, Code Is Data
decidability, Decidability – Decidability
encoding, Encoding
infinite looping, Universal Systems Can Loop Forever – Universal Systems Can Loop Forever
lambda calculus and, Lambda Calculus – Lambda Calculus
performing algorithms, Universal Systems Can Perform Algorithms – Universal Systems Can Perform Algorithms
programs standing in for, Programs Can Stand In for Turing Machines , Programs Can Stand In for Turing Machines
simulation, Simulation

Other books

Wooden Ships by Donald Piazza

The Bad Boy's Baby (Hope Springs) by Cindi Madsen

No World Concerto by A. G. Porta

Stronger than Bone by Sidney Wood

What a Girl Wants by Lindsey Kelk

Cast Iron Cover-Up (The Cast Iron Cooking Mysteries Book 3) by Jessica Beck

Sheltering Hearts by Robyn Carr

The Gamer's Wife by Careese Mills

Foolproof by Diane Tullson

Love and Let Die by Lexi Blake