4 events with tag "computability"
1936
ID: 370
Alonzo Church proves the undecidability of first-order logic (Church's Theorem) and develops lambda calculus
ID: 370
1936
ID: 371
Alan Turing publishes 'On Computable Numbers', introducing Turing machines and proving the halting problem is undecidable
ID: 371
1936
ID: 4612
Alan Turing invents Turing machine - mathematical model of computation, defines algorithm
ID: 4612
1966
ID: 4544
Wang proves tiling undecidability - no algorithm can determine if a set of tiles can tile the plane
ID: 4544