# 7th Black Board Day (BBD7)

2012/05/03

Last Sunday (April 29th) was the Black board day (BBD), which is a small informal workshop I organize every year. It started 7 years ago on Kurt Gödel‘s 100th birthday. We discuss logic, computation, math, and beyond. This year happens to be Alan Turing‘s 100th birth year, so we had a theme that combines Turing machines and logic. It was a huge success thanks to special guest speakers.

### Il Memming Park: On halting problem route to incompleteness

I was trying to give an overview on how certain problems in mathematics that deals with natural numbers are very difficult, and why a mechanized theorem prover was a dream of Hilbert’s. Then I introduced the devilish diagonal argument of Cantor’s in the context of binary strings and languages. Basically, there are more languages (defined as a set of finite binary strings) than there are natural numbers. I introduced Turing machines and their 3 possible outcomes (accept, reject, and infinite loop) as well as the concept of universal turning machines. Then, I constructed the halting problem and showed that the diagonal argument prevents us from having a Turing machine that can tell if another Turing machine will stop or not in finite time. Unfortunately, I didn’t have enough time to elaborate how the halting problem has a similar structure to the proof of incompleteness theorem, and how they could be connected.

### Kenneth Latimer: On Roger Penrose’s Emperor’s new mind

The controversial book Emperor’s new mind (1989) is famous for extending Lucas’ idea that since Turing machines can’t know if the Gödel statement is true, while human does, the computability of human must be greater. He further linked that idea to physics and brain. During our discussion, we agreed that the Gödel statement is true, but it’s truth can only be judged outside of the system, and human certainly are not using the same set of axioms as the system that the Gödel statement is constructed on. And also, the fact that we do not understand certain physics doesn’t imply that the is not computable. It was interesting that two people (Memming and Jonathan) were initially drawn into neuroscience because of this book.

### Michael Buice: Algebra of Probable Inference

Michael started talking about adding oracles to Turing machines, and the hierarchy of such oracle-equipped Turing machines, as well as Kleene hierarchy of logical statements, but quickly jumped into a new topic. Instead of only considering only True or False statements, if we allow things in between, with a reasonable assumptions we can derive axioms of probability theory. Heuristically speaking, Gödel’s incompleteness theorem would imply that there are statements that even with infinite observations, the posterior probability for the statement does not converge to 0 or 1 and always stay in between. The derivation is given in Richard Cox’s papers, and the theory was expanded by Jaynes.

### Ryan Usher: An Incomplete, Inconsistent, Undecidable and Unsatisfiable Look at the Colloquial Identity and Aesthetic Possibilities of Math or Logic

Ryan started by stating how he finds beauty in mathematical proofs, especially in Henkin’s completeness theorem. But then he was unsatisfied with the fact that how often beautiful results such as Gödel’s incompleteness theorem are abused in completely irrelevant contexts such as in economics and social sciences. He had numerous quotes and examples showing the current state of sad abuses. He claimed that this is partly because of the terms like “consistency”, “completeness” have very rigorous meanings in mathematical context but often people associate their meanings to the common sensical ones.

### Jonathan Pillow: Do we live inside a Turing machine?

Jonathan summarized the argument by Bostrom (2003) that it is very probable that we are living inside a simulation. Under the assumption that

- Simulated human brain brings consciousness (“substance independence”)
- Large scale simulation of human brain + physical world around human is possible

Then, assuming high probability of technological advancement for such simulation, and some grad student in the future wishing to run “ancestor simulation”, a simple counting argument of all humans in simulation and not shows that we are probably living in a simulation. (Below photo is Jonathan’s writing. It was a white board, but in the spirit of black board day, I inverted the photo.)

References:

- Alan Turing. (1936) On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. 2 42: 230
- Michael Sipser. Introduction to Computation (Memming’s halting problem proof followed this one)
- Roger Penrose. Emperor’s new mind
- Torkel Franzén. Godel’s Theorem: An Incomplete Guide to Its Use and Abuse (recommended by Ryan)
- Richard T. Cox. Algebra of Probable Inference
- Cox, R. (1946). Probability, frequency and reasonable expectation. American Journal of Physics, 14(1), 1–13.
- E.T. Jaynes. Probability Theory: The Logic of Science
- Martin Davis. The Undecidable (Collection of papers) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (Dover Books on Mathematics)
- Martin Davis, Computability and Unsolvability (Michael Buice: One of the most beautiful books written by humankind; introduction to recursive function theory and computability, turing machines. One of the few books which does so in a complete and rigorous manner, also covers Logic and Gödel’s theorem.)
- Bostrom, N. , 2003, Are You Living in a Computer Simulation?, Philosophical Quarterly (2003), Vol. 53, No. 211, pp. 243-255.

Advertisements

## Trackbacks