Computing Beyond Turing

CISC-490 Topics in Computing Science

CISC-879 Topics in Theoretical Computing

Fall Term 2021

http://www.cs.queensu.ca/home/akl/cisc490-cisc879/2021/info21.html

This page provides information on the course. It tells you about the instructor, teaching assistant, course schedule, course requirements, and method of grading. It also contains a course description, course material, assignments, and some important dates.

Instructor
| Office
| E-mail
| Phone |

Selim Akl | 722 Goodwin Hall | akl@cs.queensu.ca
| 36062 |

One session per week is scheduled for this course as follows:

Day
| Time
| Place | |

Thursday | 6:30 p.m. - 9:00 p.m. (3 x 50 min = 150 min) | STIRLG 401 | |

I will be glad to meet with you any time you need to see me in my office. Please talk to me in class to arrange an appointment.

In case you have a concern, then:

1) If you are a CISC-490 student, please address your questions to the teaching assistant for the course:

Jia He Sun

Office hours: Wednesdays, 1:00 - 3:00 p.m. in Goodwin Hall 248.

2) If you are a CISC-879 student, please send your questions to me.

Here is what you are expected to do in this course:

1. Attend the weekly lecture.

2. Do all the assignments (you do not need to hand in your weekly work).

3. Complete a course project (your mark on the course will be based on this component).

An introduction to computation beyond the Turing machine model. Several topics in the field of unconventional computing are covered, including parallel, quantum, and bio-molecular algorithms, cellular automata, non-standard computational problems, computations in nature, and non-universality in computation. The emphasis is on computational models, design of algorithms and mathematical analysis.

The main themes of this course are:

(1) The future of computing is umconventional computation

(2) Parallel processing is at the center of unconventional computation

(3) Nonuniversality in computation follows from (1) and (2).

For CISC-490: A minimum grade of B+ in CISC-365 and registration in a Computing plan.

For CISC-879: A minimum grade of B+ in an undergraduate course on the design and analysis of algorithms.

1. Textbook

S.G. Akl, Parallel Computation: Models and Methods, Prentice Hall, Upper Saddle River, New Jersey.

2. Papers:

The papers to read for the assignments are available here.

Week
| Starting
| Material covered, Assignment for next week (readings and problems to work on) |

1 | Sept 9 | Course overview (schedule, topics, grading method), Introduction to parallel and unconventional computation, Assignment 1 |

2 | Sept 16 | Models of Computation, Unconventional paradigms and nonuniversality in computation, Assignment 2 |

3 | Sept 23 | Combinational Circuits, The role of time in computation, Assignment 3 |

4 | Sept 30 | Parallel Prefix Computation, Cellular automata, Assignment 4 |

5 | Oct 7 | Divide and Conquer, Sensor networks, Assignment 5 |

6 | Oct 21 | Pointer-Based Data Structures, Quantum computation, Assignment 6 |

7 | Oct 28 | Linear Arrays, Quantum cryptography, Assignment 7 |

8 | Nov 4 | Meshes and Related Models, Nature computes, Assignment 8 |

9 | Nov 11 | Hypercubes and Stars, Information and energy, Assignment 9 |

10 | Nov 18 | Models Using Buses, The meaning of life, Assignment 10 |

11 | Nov 25 | Broadcasting with Selective Reduction, Parallel Synergy, What is compuation?, Assignment 11, Assignment 12 |

12 | Dec 2 | Conclusion: Unconventional computation, current state and future prospects. |

Note: The week of October 11-15 is the Fall mid-term Break. There will be no lecture on October 14, 2021.

Working on the problems and completing the readings are very important activities: They are essential to a successful completion of the course project.

- Assignment 1: Read Preface and Sections 1.1-1.4, solve problem 1.16. Read papers 1, 2, and 36.
- Assignment 2: Read Sections 2.1-2.4, solve problems 2.6, 2.8, (and problem 2.9 for CISC-879 students only). Read papers 3, 15, and 37.
- Assignment 3: Read Sections 3.1-3.4, solve problem 3.22. Read papers 12 and 4.
- Assignment 4: Read Sections 4.1-4.8, solve problem 4.20 (and problem 4.22 for CISC-879 students only). Read papers 10, 11, 38 and 39.
- Assignment 5: Read Sections 5.1-5.4, solve problem 5.16. Read papers 7, 21 and 22.
- Assignment 6: Read Sections 6.1-6.3, solve problem 6.4. Read papers 6, 8 and 27.
- Assignment 7: Read Sections 7.1-7.3, solve problem 7.6 (and problem 7.15 for CISC-879 students only). Read papers 17, 18 and 40.
- Assignment 8: Read Sections 8.1-8.3, solve problem 8.12 (and problem 8.15 for CISC-879 students only). Read papers 14 and 41.
- Assignment 9: Read Sections 9.1-9.2, solve problem 9.2 (and problem 9.7 for CISC-879 students only). Read papers 24, 25, and 31.
- Assignment 10: Read Sections 10.1-10.3, solve problem 10.16 (and problem 10.45 for CISC-879 students only). Read paper 19 and 42.
- Assignment 11: Read Sections 11.1-11.3, solve problem 11.6 (and problem 11.9 for CISC-879 students only). Read papers 30 and 32.
- Assignment 12: Read Sections 12.1-12.6, solve problem 12.17 (and problem 12.23 for CISC-879 students only). Read papers 28 and 35.

For your course project, you are required to write (and submit to me by email) a report on a number of papers selected from a list.

The list of papers for the course project will be posted here in the third week of November and removed in the first week of December.

Your report, in PDF format, is due to me by 5 p.m. EST on Friday, December 17, 2021.

**CISC-490 students**: Select from the list at least two papers, covering different topics.
The total length of the selected papers should be at least 30 pages.
Your report should be 20 pages long, double spaced in 12pt type and 1 inch margins.
The report is to include: a cover page, a one-page summary, the main body, a conclusion, and a list of references.
The main body is to include the following parts for each paper you selected: a description of the paper's contents and a critique of the paper
(advantages and disadvantages). Because parallelism is central to computing beyond Turing, the role played by parallel computation in each paper selected
for the project is to be emphasized.
Your report may also include any improvements you could suggest.

**CISC-879 students**: Select from the list at least three papers, covering different topics.
The total length of the selected papers should be at least 40 pages.
Your report should be 30 pages long, double-spaced in 12pt type and 1 inch margins.
The report is to include: a cover page, a one-page summary, the main body, a conclusion, and a list of references.
The main body is to include the following parts for each paper you selected: a description of the paper's contents and a critique of the paper
(advantages and disadvantages). Because parallelism is central to computing beyond Turing, the role played by parallel computation in each paper selected
for the project is to be emphasized.
Your report may also include any improvements you could suggest.

All information about Quantum Chess is available here.

Here are my two short stories on the future of computing: Information and Computation: The Essence of It All, and Time: The Final Frontier.

An example illustrating the memory access unit for the Broadcasting with Selective Reduction model of computation is available here.

Available as well is a summary of the texbook.

CISC-490 students: The web page on standard syllabus elements is part of this syllabus; you are expected to be familiar with everything on that page.

THE QUEEN'S SCHOOL OF COMPUTING IS COMMITTED TO EQUITY, DIVERSITY, INCLUSION, AND INDIGENEITY.