COMPUTABILITY, UNSOLVABILITY, and CONSCIOUSNESS
# COMP 006, Spring 2004

## COMPUTABILITY, UNSOLVABILITY, and CONSCIOUSNESS

# Web Links

TURING MACHINES
The Alan Turing Home Page

Alan Turing

ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM
(Turing 1936 paper)

*Turing Machines (AMS)

*Turing Machines

Topics Related to Turing Machines

*Formal Definition of Turing Machines

*Transition Function, Instantaneous Descriptions, and Moves

*Programming a Turing Machine

*Turing Machines as Acceptors

*Recognizing a Language

*Turing Machines as Transducers

*EXAMPLES AND VARIETIES OF TURING MACHINES
Sorting

Virtual Turing Machine (VTM)

Turing Machines implemented in JavaScript (Examples)

TuringKara - two-dimensional Turing machines

Wolfram's Version of Turing machines

Example Turing Machines

Two Dimensional Turing Machines (from Wolfram)

Langton's Ant (A two-dimensional Turing machine)

Turmite simulations

A random pattern produced by a Turmite

Turing Machine implemented in Conway's Game of Life

John Conway's Game of Life

Patterns, Programs, and Links for Conway's Game of Life

THE POWER OF TURING MACHINES
*Variations on Turing Machines, Universal Turing Machines,
Church-Turing Thesis

Recursively Enumerable Languages

Church's Thesis

*Church-Turing Thesis

The Church-Turing Thesis

A Universal Turing Machine

Universal Turing Machine

Primitive Recursive Functions

Recursive Functions

Ackermann function

UNSOLVABILITY
Halting Problem

Halting Problem

!The Halting Problem and Other Unsolvable Problems

Uncomputable Functions and Church's Thesis

Uncomputability in the work of Turing and Penrose

Discussion of unsolvability of Hilbert's tenth problem

Rice's theorem

Bounds on the Busy Beaver Function

Proof of Uncomputability of the Busy Beaver Function

Busy Beaver Simulations

References on the Busy Beaver Function

Busy Beaver Function (Wolfram's Version)

Busy Beaver Candidates for 4-tuple Turing machines

Chaitin's Constant

Chaitin's Constant

HYPERCOMPUTATION
Hypercomputation

Hypercomputation: computing more than the Turing machine

Wave-particle duality

Double-slit experiment

Schrödinger's cat

Uncertainty principle

Tunneling

Quantum Superposition

Quantum Superposition

Decoherence

Decoherence in Large Molecules

Quantum Wierdness

Quantum computation: a tutorial

The Quantum Computer

Quantum Leaps May Solve Impossible Problems

Quantum Algorithm for Hilbert's Tenth Problem

The quantum algorithm of Kieu does not solve the Hilbert's tenth problem

Light Exceeds Its Own Speed Limit, or Does It?

Is Faster Than Light Travel or Communication Possible?

Quantum Entanglement On A Chip Is Demonstrated

Applications of Quantum Entanglement

MATHEMATICAL LOGIC
Euclidean Geometry

Euclid's Postulates

The Axioms of Euclid and Hilbert

Euclid's Elements

Aristotelian Logic

Aristotelian Logic

Syllogism

Categorical Syllogisms

Twenty Four Valid Categorical Syllogisms

Propositional calculus

First-order predicate calculus

Set Theory

Axiomatic set theory

Zermelo-Fraenkel Set Theory

The Peano Axioms

Higher-order logic and nonstandard models

Nonstandard Models

Logical Systems

Gödel's incompleteness theorem

Gödel's Incompleteness Theorem

Discussion of Gödel's theorem and other incompleteness results

Algorithmic information theory

Gödel's Theorem and Information (Chaitin's View)

A Century of Controversy over the Foundations of Mathematics (Chaitin)

THE UNKNOWABLE (Ad for Chaitin book)

Transfinite Numbers

PHILOSOPHICAL ISSUES
The Emperor's New Mind (Penrose book attaching foundations of AI)

Turing's Test

Turing's Test

A Paradox of Consciousness

Minds, Machines, and Goedel

The Goedelian Argument

Limitations of Self Knowledge

Minds, Machines, and Mathematics

The Non-Algorithmic Character of Human Consciousness

Consciousness Involves Noncomputable Ingredients

Why Penrose is Wrong about the Computability of Human Mathematics

The Chinese Room Argument

LECTURE NOTES (SPORADIC)
Questions Considered in This Course

Example Turing machines

Modified Turing machines

Decidability and Partial Decidability

Undecidability

Hypercomputation

Consciousness

Logic

Incompleteness

Survey of Course

Slides with Animations

Course Projects