Скачать или смотреть MATH 1090 - 6 1 02 Uncomputable

Computational problems, machines, and inputs
Computable ∃ Alg A, ∀ Inputs I, A(I)=P(I)
Uncomputable ∃P∀M∃I M(I)≠P(I)
Table Look Up vs TM ∀k∃Mtable∀x,y≤k Mtable(x,y)=x×y vs ∃M∀x,y M(x,y)=x×y
Probabilistic Algorithms ∃M∀I PrR[M(I,R)≠P(I)] ≤ 2-|R|
Time Complexity ∃M∃c∀I M(I)=P(I) and Time(M,I)≤ |I|c
Classifying Functions f(n)∈O(g(n)) ≡ ∃c∃n0∀n≥n0 f(n) ≤ cg(n)
Coding Phase vs Execution Phase ∃ Alg A, ∃ # k, ∀ Inputs I, ∃ time t, A(I)=P(I) & Lines(A,I)=k & Time(A,I)=t
Compiling Java to TM ∀ Java Programs J, ∃ TM M, ∀ input I, J(I)=M(I)
Universal TM ∃ TM MU, ∀ TM M, ∀ input I, MU(M,I) = M(I)
Hugely Expressive There is a first order logic sentence Compute(J,I,y)
that states computer program J on input I outputs y.