CS:APP-ch11 Network Programming
11.1 The Client-Server Programming Model
4 steps of client-server transaction
あなたには僕が見えるが?
BIG-O AND SMALL-O NOTATION
$ f(n) = O(g(n)) \ \Longleftrightarrow f(n) \ \le cg(n) $
$ f(n) = o(g(n)) \ \Longleftrightarrow f(n) \ \lt cg(n) $
polynomial bounds: with the form $ n^c $
exponential bounds: with the form $ 2^{ ( n^{\delta} ) } $
Time complexity
Making machines that reproduce themselves.
SELF-REFERENCE
Construct $ SELF $ prints out a copy of its own description.
LEMMA 6.1
define computable function $ q : Σ^ ∗\longrightarrow Σ ^ ∗ $
$ SELF $
If A reduces to B
$ A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable) $
$ A \ (undecidable) \longrightarrow B \Rightarrow B \ (undecidable) $
General Idea
Contradiction on $ A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable) $
If we have a TM R that decides $ HALT_{TM} $ ( or sth ).
Then we can use R to construct a TM S that decides $ A_{TM} $
thus obtain a contradiction.
Recall:
Recognizer
Decider
DECIDABLE PROBLEMS CONCERNING REGULAR LANGUAGES
$ A_{DFA} = \{ \ <B,w> \ | \ B \ is \ a \ DFA \ that \ accepts \ input \ string \ w \} $.
Proof that it’s a decidable language by designing a decider
unrestricted access to unlimited memory
The Turing machine model uses an infinite tape as its unlimited memory.
It has a tape head that can read and write symbols and move both left and right on the tape.
The outputs accept and reject are obtained by entering designated accepting and rejecting states. If it doesn’t enter an accepting or a rejecting state, it will go on forever, never halting.
DEF
In this chapter we present context-free grammars to describe certain features that have a recursive structure.
help us organize and understand relationships of terms.
Application: compilers and interpreters
establishing new languages and implement these languages by constructing evaluators.
(极简版)
evaluators ( interpreter )
metacircular
System decomposed into computational objects with time-varying state
language must provide an assignment operator to enable us to change the value
3.1.1 Local State Variables
model the situation of withdrawing money from a bank account
1 2 3 4 5 6 | (define (make-withdraw balance) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds"))) |