COSC 494/594
Unconventional Computation
Fall 2019
Instructor:
Bruce MacLennan [he/his/him]
Phone: 974-0994
Office: Min Kao 550
Office Hours: MW 2:30–3:30, or make an
appointment
Email:
maclennan AT utk.edu
GTA:
Michael
Price
Office: Min Kao 313
Hours: MW 12:30–1:30,
or make an appointment
Email: mprice35
at vols.utk.edu
Classes: 11:15–12:05 MWF, MK 405
Directory of Handouts, Labs, etc.
This page: http://web.eecs.utk.edu/~bmaclenn/Classes/494-594-UC/
Information
Description
Unconventional computation
(or non-standard computation)
refers to the use of non-traditional technologies and computing
paradigms. As we approach the limits of Moore’s Law, progress in
computation will depend on going beyond binary electronics and on
exploring new paradigms and technologies for information
processing and control. This course surveys some potential
approaches to post-Moore’s Law computing.
Potential topics include quantum computation and quantum
annealing; optical computing; analog computing; DNA, RNA, peptide,
and general molecular computation; chemical computing;
reaction-diffusion systems; liquid-state machines; amorphous
computing; membrane computing and P systems; single organic
molecule computing; computational mechanics; ballistic computing;
reversible computing; spatial computation; cellular automata;
cellular neural nets; neurocomputers; organic computation; natural
computation; physarum computers; emergent computation;
hypercomputation; non-Turing computation.
Prerequisites
I intend this course to be accessible to all upper-division
undergraduate and graduate students in computer science, computer
engineering, electrical engineering, mathematics, physics, and
similar disciplines. To get the most out of the course,
undergraduate CS majors should have completed the 300-level
required courses. Students will be expected to be familiar with linear algebra. If you have
any questions about whether you should take this course, please email me.
Students taking the course for graduate credit (COSC 594) will be
expected to do specified additional work, including an in-class
presentation.
Grading
There will be a mixture of homework, simulation experiments, and
a term paper. Graduate students will be expected to do an in-class
presentation. Occasional pop quizzes will count for 10% of your
grade.
Text
The text is the current draft of my book in progress, Lecture
Notes in Unconventional Computation [pdf], which will be posted in
sections below (Tentative List
of Topics). Typically we cover 1–5 in this list.
Student Learning
Outcomes
Click
here.
Accommodations
- For Students with Disabilities
Students who have a disability that requires accommodation(s)
should make an appointment with the Office of Disability Services
(974-6087) to discuss their specific needs as well as schedule an
appointment with me during my office hours.
- Name and Pronoun Accommodations
If you use a name and/or pronouns other than what is in the course
roll, please email me
with the name and/or pronouns that you would like me to use and I
will be glad to accommodate this request.
Tentative List of Topics
- Introduction [UC-I.pdf]
- Post-Moore’s law computing
- Embodied computing
- Super-Turing vs. non-Turing computation
- Physical information
processing
- Energy dissipation [UC-IIA.pdf]
- Thermodynamics of computation [UC-IIB.pdf]
- Reversible computing [UC-IIC.pdf]
- Quantum computation
- Mathematical preliminaries [UC-IIIA.pdf]
(see also complex number review [FFC-ch4])
- Basic concepts from quantum theory [UC-IIIB.pdf]
- Introduction
- Postulates of QM
- Wave-particle duality (supplementary)
- Superposition
- No-cloning theorem
- Entanglement & EPR paradox
- Uncertainty principle (supplementary)
- Quantum information [UC-IIIC.pdf]
- Qubits & secure key distribution
- Quantum gates
- Quantum circuits
- Quantum gate arrays
- Quantum parallelism
- Applications: Superdense coding and quantum
teleportation
- Universal quantum gates
- Quantum algorithms
- Deutsch-Jozsa [UC-IIID1.pdf]
- Simon [UC-IIID2.pdf]
- Shor [UC-IIID3.pdf]
- Grover & heuristic search [UC-IIID4.pdf]
- Quantum error correction [UC-IIID5.pdf]
- Abrams-Lloyd theorem [UC-IIIE.pdf]
- Quantum annealing [slides: UC-III.QA1.pdf, UC-III.QA2.pdf (Andrew
Child’s slides)]
- Universal quantum computers (supplementary) [UC-IIIF.pdf]
- Feynman
- Benioff
- Deutsch
- Physical realizations (supplementary)
- Quantum probability in cognition [UC-IIIG.pdf]
- Molecular computation
- Basic concepts [UC-IVA.pdf]
- DNA basics
- DNA manipulation
- Filtering models [UC-IVB.pdf]
- Adleman
- Lipton
- Test tube programming language
(supplementary)
- Parallel filtering model (supplementary)
- Formal models [UC-IVC.pdf]
- Sticker systems
- Splicing systems (supplementary)
- Enzymatic computation [UC-IVD.pdf]
- Analog computation (read
sections A–B)
- Definition and history [UC-VAB.pdf]
- Fundamentals of analog computing (supplementary) [UC-VCD.pdf]
- Analog computing in nature (supplementary)
- General purpose analog computation (supplementary) [UC-VEFGH.pdf]
- Analog computation and the Turing limit (supplementary)
- Analog thinking and future directions (supplementary)
- Analog solution of k-SAT [Analog k-SAT.pdf]
- Spatial computation
- Cellular automata
- Cellular neural networks
- Computing with solitons etc.
- Reaction-diffusion computing
- Biocomputing
- Physarum machines
- Unstructured computation
- Liquid-state machines
- Reservoir computing
- Amorphous computing
- Blob computing
- Self-assembling systems
- Other potential topics
- Field computation
- Optical computing
- Carbon nanotubes
- Spintronics
- Relativistic computing
- Abstract geometrical computation
- Arithmetical hierarchy
- Algebraic TM computation
- Infinite-time computation
- Student presentations
- Membrane
System / P System (Tasmia Rahman Tumpa)
- Oracle
Turing Machines (Pengxiang Xu)
- The
D-Wave Computer: Practical Quantum Computing (Paula Olaya)
- Quantum
Machine Learning (Gerald Jones)
- Memristors and
Beyond (Nick Skuda)
Assignments
Simulators
Online Resources
- Unconventional and
Non-standard Computing in general:
- Quantum Computing:
- Miscellaneous
Return to MacLennan’s
home page
Send
mail to Bruce MacLennan / MacLennan@utk.edu
This page is web.eecs.utk.edu/~bmaclenn/Classes/494-594-UC
Last updated: 2019-12-16.