Tom with puzzle

Honors Class Informatics

Fall 2013-2014

[Update Not Yet Completed]

[ Schedule | Assignments | Literature | Downloads ]

A N N O U N C E M E N T S
07-Apr-2014Please join the course in peach3.
Use your TU/e account information.

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

Schedule

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

Timing
17:30 - 17:45Get together in ...
17:45 - 18:15Dinner in Auditorium
18:15 - 21:00Class in ?? of AUD

Color Legend
Tentative No class Class completed Next upcoming class

LectureDateTopic
-Mon 21 Apr 2014 TU/e closed
-Mon 28 Apr 2014 No class
-Mon 05 Apr 2014 TU/e closed
1Mon 12 May 2014 Information Theory,
Compression, Protection
2Mon 19 May 2014 From Formula to Algorithm,
Automaton, Grammar
3Wed 28 May 2014 Limits of Computability,
Universality
4Mon 02 Jun 2014 Intrinsically Hard Problems,
Randomization
519 Jun 2014 Nature Computes,
DNA Computing,
Quantum Computing

Assignments

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

To Be Supplied

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

[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 Table of Contents, Ch.1, 2, and 4 as PDF, errata, etc.
[See this book at Amazon.com]
Wikipedia article about this book

[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

[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.

[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.

[R] Randomness
Dilbert and the random number generator
  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)
    int getRandomNumber() { return 4; /* chosen by fair dice roll; guaranteed to be random */ }
  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, Sept. 2011.
  10. A Memristor True Random-Number Generator, IEEE Spectrum, Yu-Tzu Chiu, 12-Nov-2012

[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.


©2014, Tom Verhoeff (TUE)
Feedback about this page is welcome