. Foundations : partial, total functions
. Undefined operation(Error termination)
ex) division by zero
. 3/0 has no value - mathematically undefined
. imprementation may halt with error condition
. Evalutino of the expression cannot proceed because of a conflict between operator and operand.
. Nontermination - 무한루프, divergenece 등
. f(x) = if x = 0 then 1 else f(x -2)
. This is a partial function : not defined on all arguments
. cannot be detected at compile-time; This is halting problem
. proceeds indefinitely
. These two cases are
. Mathematically equivalent
. Operationally different
. Partial and total functions
. Total function : f(x) has a value for every x
. Partial functino : g(x) does not have a value for every x
. 우리가 푸는 것은 recursive partial function이므로 못 푸는 문제가 존재한다.
. Functions and graphs
. mathematics : afunctions is a set of ordered pairs(graph of function)
. Partial and total functions
. total function f: A->B is a subset f in AxB with
. For every x in A, there is some y in B with (x,y) in f (total)
. If (x,y) in f and (x, z) in f then y = z (single-valued)
. partial function f: A->B is a subset f in AxB with
. If (x,y) in f and (x, z) in f then y = z (single-valued)
. programs define partial functions for two reasons
. partial operations (like division) - 바로 termination가능
. nontermination
f(x) = if x = 0 then 1 else f(x-2)
. Halting problem
. Computable
. Partial recursive functinos(recursion을 허용하는 partial function)
. = Lambda calculus
. = Turing machine
. symbol manipulating devices
. Tape, head, state register, action table(transition function)으로 구성
. Halting problem(A noncomputable function)
. Given a program P that requres exactly one string input and
a string x, determine whether P halts on input x.
(Say yes or no)
. Undecidable - dkanfl aksgdms tlrksdmf wnjeh dkf tn djqtek.
. Computability
. Definition
Function f is computable if some program P coumputes it:
For any input x, the computation P(x) halts with output f(x)
. Terminology
. Partial recursive functions
= Partial functions (int to int) that are computable
. Halting function
. Decide whether program halts on input
. Given program P and input x to P
. Halt(P, x) = yes if P(x) halts, no otherwise
. Clarifications
. Assume program P requires one string input x
Write P9x) for output of P when run in input x
Program P is string input to Halt
. Fact : There is no program for Halt.
. Unsolvability of the halting problem
. Suppose P solves variant of halting problem
. On input Q, assume, P(Q) = yes if Q(Q) halts, no otherwise
. Build program D - P로 D를 만들자
. D(Q) = run forever if Q(Q) halts, if Q(Q) runs forever
. Does this make sense? What can D(D) do?
. If D(D) halts, then D(D) runs forever.
. IF D(D) runs forever, then D(D) halts
. Contradiction : program P must not exist
. Main points about computability
. Some functions are computable, some are not
. Halting problem
. Programming langage implementation
. Can report error if program result is undefined due to division by zero, other undefined basic operation
. Cannot report error if program will not terminate
. RE(Regular expression) < CFG(Context Free Grammar)
< TM (Turing Machine) != not computable
. RE = DFA, NFA, e-DFA
. RE + stack = Push-down automata = CFG
. CFG + Tape = TM = Computable
. Diversion
. C : Kills the people once saved
. C++ : The empire strikes back
. Java - Don't drink don't smoke - what do you do?
. C++이 복잡해서 필요한 것만 넣음.
strong typed, 그런데 결국은 다시 복잡해짐.
. Perl : Feel free to substitute your favorite error prone language
. scripting language
. Automating simple computer tasks
. Connecting diverse pre-existing components to accomplish a new related task
. Rapid development