Honors Class Informatics

Fall 2013-2014

[ Schedule | Assignments | Literature ]

This course is part of the TU/e Honors Horizon Program 2013-2014 (last year old style).

Course introduction

Schedule

The assignments shown in the table are due before the lecture.

Assignments

Work for some assignments is to be handed in via peach. Deadlines are shown in peach.

1. [Deadline: 12 May 2014] Read Sections 1, 2, 5, and 6 of Informatics Everywhere.
   Note that there is also an Addendum.
2. [Deadline: 19 May 2014] Read about Tom's JavaScript Machine and start on the Challenge of writing a self-reproducing program for it. Your goal is to get as far as Hint 8.
3. [Deadline: 19 May 2014] Text analysis and entropy
4. [Deadline: 01 Jun 2014] See peach, Assignment Set 3.
5. [Deadline: 01 Jun 2014] Continue with the Challenge of writing a self-reproducing program for it. Your goal is to get as far as Hint 13.
6. [Deadline: 11 Jun 2014] See peach, Assignment Set 5.
7. [Deadline: 16 Jun 2014] Continue with the Challenge of writing a self-reproducing program for it. Your goal is to get as far as Hint 28. If you are patient, and press on to Hint 40, then you will reach the Afterthoughts (and a new, more impressive, Challenge).

Literature

[AA]

Juraj Hromkovic.
Algorithmic Adventures: From Knowledge to Magic.
Springer-Verlag, 2009.
[See this book at Google Books]
[See this book at Amazon.com]
Also see under Downloads (access restricted to TU/e domain).

[NoC]

Cristopher Moore and Stephan Mertens.
The Nature of Computation.
Oxford Press, 2011.
Also see under Downloads for Ch.7 (The Grand Unified Theory of Computation) (access restricted to TU/e domain).

[GEB]

Douglas R. Hofstadter.
Gödel, Escher, Bach: An Eternal Golden Braid.
Basic Books, 1979, 20th anniversary edition 1999.
[See this book at Amazon.com]
Wikipedia article about this book

From a review:

"Besides being a profound and entertaining meditation on human thought and creativity, this book looks at the surprising points of contact between the music of Bach, the artwork of Escher, and the mathematics of Gödel. It also looks at the prospects for computers and artificial intelligence (AI) for mimicking human thought. For the general reader and the computer techie alike, this book still sets a standard for thinking about the future of computers and their relation to the way we think."

[AMT]

Andrew Hodges.
Turing: a natural philosopher.
Routledge, 1999.
[See this book at Amazon.com]

A short (some 60 pages) but complete biography of Alan Turing, by the author who earlier wrote a more extensive biography, titled Alan Turing: The Enigma (an ambiguous title, alluding to both the German Enigma Cipher that Alan Turing helped break, and the mysterious nature of his person). Unfortunately, it does not mention Turing's work on embryology, other than listing a paper he wrote in 1952, titled ''On the Chemical Basis of Morphogenesis'').

Alan M. Turing (in Wikipedia)

Turing Machine (in Wikipedia)

[LSS]

Rudy Rucker.
The Lifebox, the Seashell, and the Soul: What Gnarly Computation Taught Me About Ultimate Reality, the Meaning of Life, and How to Be Happy.
Basic Books, 2006.
Lifebox Home Page; there you can find the entire book, errata, etc.
[See this book at Google Books]
[See this book at Amazon.com]

[WW]

Ch.25, "What is Life?", pp.927-961 from:
Winning Ways for Your Mathematical Plays, Volume 4.
by E.R. Berlekamp, J.H. Conway, R.K. Guy.
[See this book at Google Books]
[See this book at Amazon.com]

This chapter is about Conway's Game of Life and explains why this "game" is universal. See Downloads.

[GoL] Game of Life and other (Cellular) Automata

1. Wikipedia article about Conway's Game of Life
2. Conway's Game of Life at ExperimentGarden: a brief introduction
3. What is the Game of Life?: another brief introduction, with runnable examples through an embedded Java applet (no need to install software)
4. Golly: a program to explore Conway's Game of Life on various platforms (Linux, Mac OS X, Windows); includes many complex patterns
5. Cellular Automaton (Wikipedia article); especially, see the Wolfram classification with Rule 30 and Rule 110 as interesting examples

Nature Computes

1. A Single-Atom Magnet Breaks New Ground for Future Data Storage École Polytechnique Fédérale de Lausanne, 15-Apr-2016.
2. Paving The Way For Light-Based Circuits, Asian Scientist, 07-Dec-2016.
3. IBM fits a bit on an atom, eyeing ever-smaller devices, Computerworld, by Stephen Lawson, 08-Mar-2017.
4. Will energy-free computing reactions ever take place? [alternative link], FETFX, by Alexander Hellemans, 2-Nov-2017.
5. World’s Smallest Atom-Memory Unit Created, UT News, 19-Nov-2020.
6. New Extremely Energy-Efficient Optical “Transistor” Speeds Up Computation Up to 1,000 Times, SciTechDaily, Skoltech, 24-Sep-2021. Also see: Single-photon nonlinearity at room temperature
7. Information Could Be the Fifth State of Matter, Proving We Live in a Simulation, Popular Mechanics, by Manasee Wagh, 30-Mar-2022.

[QC] Recent News about Quantum Computing

1. Super-Fast Quantum Computer Gets Ever Closer: Quantum Particles Pinned Down, in ScienceDaily, 9-Nov-2009:

   "Researchers at the Kavli Institute for Nanosciences at Delft University of Technology, have succeeded in getting hold of the environment of a quantum particle. This allows them to exercise greater control over a single electron, and brings the team of researchers, led by Vidi winner and FOM workgroup leader Lieven Vandersypen, a step closer still to the super-fast quantum computer."

2. NIST Demonstrates 'Universal' Probrammable Quantum Processor, NIST News Release, 16-Nov-2009:

   "Physicists at the National Institute of Standards and Technology (NIST) have demonstrated the first "universal" programmable quantum information processor able to run any program allowed by quantum mechanics---the rules governing the submicroscopic world---using two quantum bits (qubits) of information. The processor could be a module in a future quantum computer, which theoretically could solve some important problems that are intractable today."

3. First Programmable Quantum Computer Created, ScienceNews, 19-Dec-2009, 176(13):13 by Laura Sanders.
4. Quantum age edges closer, The Univ. of New South Wales, Australia, 05-Jan-2010.
5. Princeton scientists make a leap in quantum computing, News at Princeton, 08-Apr-2010.
6. Toshiba invention brings quantum computing closer (ELED: Entangled Light Emitting Diode), Reuters, Ben Hirschler, 02-Jun-2010.
7. World first for quantum memory storage ANU News, 24-Jun-2010.
8. 'Quantum Computer' a Stage Closer With Silicon Breakthrough, UCL News, 24-Jun-2010.
9. Optical Chip Enables New Approach to Quantum Computing, University of Bristol News, Aliya Mughal, 15-Sep-2010.
10. Quantum Computing Research Edges Toward Practicality in UCSB Physics Laboratory, Office of Public Affairs, UC Santa Barbara, 04-Oct-2010.
11. Waveguides Make Quantum Computers More Reliable, Ars Technica, Chris Lee, 15-Dec-2010.
12. TU Scientists in Nature: Better Control of Building Blocks for Quantum Computer, TU Delft, 23-Dec-2010.
13. Software Said to Match Quantum Computing Speed, IDG News Service, Joab Jackson, 23-Dec-2010.
14. New Generation of Optical Integrated Devices for Future Quantum Computers, Bristol University, 01-Mar-2011.
15. Quantum computing device hints at powerful future, BBC News, Jason Palmer, 22-Mar-2011.
16. Information Sharing at the Quantum Limit: A photon transfers its secrets onto a single atom, Max Planck Institute of Quantum Optics, 01-May-2011.
17. Long Live the Qubit!, MIT News, Larry Hardesty, 02-Jun-2011.
18. IBM's New Future: Quantum Computing, Computerworld, Patrick Thibodeau, 16-Jun-2011.
19. Why I'm Wagering $100,000 on Quantum Computing, Tech Talk, IEEE Spectrum, Scott Aaronson, 07-Feb-2012.
20. UCSB Researchers Demonstrate That 15=3x5 About Half of the Time, University of California, Santa Barbara, Andrea Estrada, 20-Aug-12.
21. UCSB Researchers Demonstrate That 15=3x5 About Half of the Time, Univ. of California, Santa Barbara, Andrea Estrada, 20-Aug-2012.
22. Quantum Chip Breakthrough to Be Unveiled, Financial Times, Ling Ge, Clive Cookson, 03-Sep-2012.
23. New Record in Quantum Communications, Australian National University, 30-Aug-2012.
24. Breakthrough in Bid to Create First Quantum Computer, University of New South Wales, Miles Gough, 20-Sep-2012.
25. Breakthrough Offers New Route to Large-Scale Quantum Computing, Princeton University, John Sullivan, 19-Oct-2012.
26. Proving Quantum Computers Feasible, MIT News, Larry Hardesty, 27-Nov-2012.
27. New chip could lead to era of ultra-fast, powerful computing, CTVNews, 03-Sep-2013.
28. New Language Helps Quantum Coders Build Killer Apps, New Scientist, Sophie Hebden, 06-Jul-2013.
29. Quantum Engineers Take a Major Step Towards a Quantum Computer, University of Bristol, Press Release, 30-Jan-2014.
30. S&T computer engineer patents quantum computing device, Missouri University Science & Technology News & Events, Mary Helen Stolz, 28-Feb-2014.
31. Silicon quantum computers will become reality say UNSW engineers, Computerworld, Hamish Barwick , 06-Oct-2015.
32. Australians Invent Architecture for a Full-Scale Silicon Quantum Computer, IEEE Spectrum, Jeremy Hsu, 30-Oct-2015.
33. Quantum computing is coming – are you prepared for it?, University of Bristol, 20-Jan-2016.
34. The Long-Awaited Promise of a Programmable Quantum Computer, MIT Technology Review, 23 Mar 2016.
35. IBM makes quantum computing available in the cloud, Computerworld, Sharon Gaudin, 04-May-2016.
36. Google moves closer to a universal quantum computer, Nature, Philip Ball, 08-Jun-2016.
37. Revealed: Google’s plan for quantum computer supremacy, New Scientist, Jacob Aron, 31-Aug-2016.
38. First ever blueprint unveiled to construct a large scale quantum computer, University of Sussex, School of Mathematical and Physical Sciences, 03-Feb-2017.
39. Manchester researchers a step closer to developing quantum computing, Univ. of Manchester, 16-Nov-2016.
40. Google is closer than ever to a quantum computing breakthrough, Futurism, Karla Lant, 23-Jun-2017.
41. Intel Accelerates Its Quantum Computing Efforts With 17-Qubit Chip, IEEE Spectrum, by Samuel K. Moore, 10-Oct-2017.
42. We’re About to Cross the “Quantum Supremacy” Limit in Computing, Futurism, 10-Sep-2017.
43. Hard computing problem might be solvable only by quantum computers, Phys.org, by Lisa Zyga, 8-Nov-2017.
44. The Case Against Quantum Computing, IEEE Spectrum, Mikhail Dyakonov, 15-Nov-2018.
45. Researchers build transistor-like gate for quantum information processing – with qudits, Purdue University News by Kayla Wiles, 16-Jul-2019.
46. Google's Quantum Tech Milestone Excites Scientists and Spurs Rivals, IEEE Spectrum, by Jeremy Hsu, 25-Oct-2019.
47. Here’s a Blueprint for a Practical Quantum Computer
 Constructing a universal quantum computer will be hard but not impossible, IEEE Spectrum, by Richard Versluis, 24-Mar-2020.
48. First Photonic Quantum Computer on the Cloud, IEEE Spectrum, Charles Q. Choi, 09-Sep-2020.
49. What Makes Quantum Computing So Hard to Explain?, Quanta Magazine, by Scott Aaronson, 08-Jun-2021.
50. Important Milestone Reached in Quantum Computing With Error Correction, SciTechDaily, Delft University of Tehcnology, 19-Dec-2021.
51. Oxford Physicist Unloads on Quantum Computing Industry, Says it's basically a scam ("In essence, the quantum computing industry has yet to demonstrate any practical utility..."), Fututism, by Victor Tangermann, 03-Sep-2022.
52. New spin control method brings billion-qubit quantum chips closer, UNSW Media, 13-Jan-2023.
53. Record-breaking quantum computer has more than 1000 qubits, NewScientist, by Alex Wilkins, 24-Oct-2023.

[MC] (Recent) News about (Bio)Molecular (DNA) Computing

1. Researchers make significant advances in molecular computing, University of Kent, 10-Dec-2009.
2. DNA computer 'ansers questions', BBC News, 05-Aug-2009.
3. Future directions in computing: DNA Computing, BBC News, 13 Nov 2007.
4. How DNA Computers Will Work, How Stuff Works
5. DNA logic gates herald injectable computers, New Scientist, 02-Jun-2010.
6. Researchers Open the Door to Biological Computers, Univ. of Gothenburg, Anita Fors, 09-Dec-2010.
7. Meet the Data-Storing Bacteria, PC World, Elizabeth Fish, 23-Dec-2010.
8. NYU Researchers Outline Method for DNA Computation in New Book New York University, James Devitt, 16-May-2011.
9. Whatever Happened to the Molecular Computer?, IEEE Spectrum, Kevin F. Kelly and Cyrus C.M. Mody, 25-Sep-2015.
10. Data Storage on DNA Can Keep It Safe for Centuries New York Times, John Markoff, 03-Dec-2015.
11. For the First Time, Signal Transfer Between Molecules Has Been Achieved, IEEE Spectrum, Dexter Johnson, 22-Sep-2017.
12. Computers of the Future May Be Minuscule Molecular Machines Live Science, Tia Ghose, 05-Apr-2017.

[R] Randomness

1. Wikipedia article on Randomness
2. At the National Institute of Standards and Technology:
   1. Random Number Generation in the Cryptographic Toolkit, which also refers you to
   2. Random Number Generation and Testing, which also offers testing software and publications like the following:
   3. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST publication SP 800-22rev1, August 2008
   4. Statistical Testing of Random Number Generators by Juan Soto (NIST), Proceedings of the 22nd National Information Systems Security Conference, October 1999. (Overview and introduction to preceding publication)
3. 'True' Randomness
   1. RANDOM.ORG: Statistical Analysis (in particular, see the Visual Analysis of the PHP rand() function)
   
4. Coin Tossing:
   1. Dynamical Bias in the Coin Toss by P. Diaconis, S. Holmes, R. Montgomery, SIAM Review 49(2):211-235 (2007, technical paper!)
   2. The Coin Flip: A Fundamentally Unfair Proposition? by James Devlin (29 March 2009; simplified exposition)
5. Gregory Chaitin. Exploring Randomness. Springer 2001.
   From the point of view of Algorithmic Information Theory.
   [See this book at Google Books]
6. W.A. Wagenaar. ''Generation of random sequences by human subjects: a critical survey of literature''. Psychological Bulletin, 77(1):65-72 (1972).
7. Resources concerning Random Number Generators
8. Truly random numbers, AlphaGalileo, 22-Feb-2010.
9. Behind Intel's New Random-Number Generator. IEEE Spectrum, Greg Taylor, George Cox, Sep-2011.
10. A Memristor True Random-Number Generator, IEEE Spectrum, Yu-Tzu Chiu, 12-Nov-2012
11. Computer scientists explore random numbers, cybersecurity, The Daily Texan, Freya Preimesberger, 07-Oct-2016.

[SR] Self-Reproduction

1. Self-reproduction challenge for Tom's JavaScript Machine
2. Wikipedia article about Quines, that is, about self-reproducing programs
3. David Madore's Discussion of Quines, which also provides a theoretical background on the universality of self-reproduction
4. RepRap, the Replicating Rapid-prototyper, an open-source 3D-printer that can construct its own parts
5. Richard Dawkins. The Blind Watchmaker: Why the evidence of evolution reveals a universe without design. 1st Ed., W.W. Norton, 1986 (book, various editions)
   Also see under Downloads
6. Gregory Chaitin about Metabiology: "to have a mathematical understanding of basic biological concepts and to be able to prove that life must evolve in very general circumstances."
7. Scientist Creates Virtual Evolution by Sharon Hill, Canwest News Service, 11-Dec-2009.
8. First Complete Computer Model of an Organism Stanford Report, Max McClure, 19-Nov-2012

[C] (Recent) News about Cryptography

1. Security Researchers Uncover SSL Vulnerability, by Sophie Curtis, eWeek Europe, 05-Nov-2009
2. How you can build an eavesdropper for a quantum cryptosystem, at 26th Chaos Communication Congress, 27-Dec-2009
3. Cellphone Encryption Code Is Divulged, by Kevin J. O'Brien, New York Times, 28-Dec-2009.
   Explains about the recent practical breaking of GSM encryption. Theoretically, it was already broken longer ago.
4. Q&A: Researcher Karsten Nohl on mobile eavesdropping, by Elinor Mills, CNet News, 01-Jan-2010.
5. What is Homomorphic Encryption, and Why Should I Care?, by Craig Stuntz, 18-Mar-2010.