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
  2. Real Computability Theory
  3. Recap on discrete complexity theory
  4. Real Complexity Theory
  5. Exact Real Computation

 

Schedule (with links to slides):

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
    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.
    1. install iRRAM on your (Linux) computer, compile and run the included example programs
 

Administration:

Host: Akitoshi Kawamura

Instructor: Martin Ziegler

Language: English

 

 

Selected References: