[PL]Ch.2 - Computable functions

. 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