Computability, Complexity, and Practice of Real Computation

Tutorial at the University of Tokyo, Jan.30 to Feb.1 (2018)

This short lecture conveys the conceptional background to contemporary computational approaches in Engineering:

Synopsis:

1. Recap on discrete computability
• Halting Problem
• un/semi/decidability/enumerability
• reduction
• WHILE programs
2. Real Computability Theory
• real numbers: binary vs. approximate
• quality, real sequences and limits
• computing real functions, Weierstrass
• comput.cost, compactness, continuity
• real arithmetic, join, maximum, integral
• root finding: uncomputable argmax
• uncomputable derivative/wave equation
• non-extensionality, discrete enrichment
3. Recap on discrete complexity theory
• Asymptotic algorithmic cost
• Complexity classes P, NP, PSPACE, EXP
• Polynomial-time reductions
• Cook-Levin Theorem
4. Real Complexity Theory
• Polynomial-time reals
• Real functions and uniform complexity
• Information-theoretic lower bounds
• (Smooth) maximization ⇔ NP
5. Exact Real Computation
• semantics: partial >, choose()
• Example algorithms: integer rounding, trisection
• iRRAM

Komaba Campus, Building #15, Room #106
Tuesday (Jan.30) to Thursday (Feb.1), 2018 Slides with animations (proprietary PowerPoint)

Assignments:

1. Write WHILE programs for
1. binary predicate x>y
2. unary predicate odd(x)
3. binary multiplication (x,y)→x×y
• Bonus if all three run in time O(log x).
For WHILE programs refer, e.g., to [Enderton'11,§1.2.3]
1. Prove that Specker's sequence is computable, but its limit is not: where t(m) := #steps the WHILE program with code m makes on input m.
2. Let a∈(0;1) be computable, f:[0;a]→R computable, and g:[a;1]→R computable with f(a)=g(a).
Prove that their join fg:[0;1]→R is again computable.
1. Let h:[0;1]→R be polynomial-time computable. Suppose P=NP.
Conclude that the real number max{h(t):t} is again polynomial-time computable.
• Bonus: Conclude that H:[0;1]∋x→max{h(t):tx} is again polynomial-time computable.
1. install iRRAM on your (Linux) computer, compile and run the included example programs