Theory of Computing

Table of contents

Title

Motivation - 1

Motivation - 2

Undecidable Problems

Definitions - 1

Definitions - 2

Hello, world - 1

Hello, world - 2

Hello, world - 3

Hello, world - 3

Reductions

Turing Machines

TMs - 1

TMs - 2

TMs - 3

TMs - 2

TM Figure

TM Formal Definition

Instantaneous Descriptions

Moves - 1

Moves - 2

Transition Diagrams

Transition Diagrams

TM Language

TMs and Halting

Storage in State - 1

Storage in State - 2

Multiple Tracks

Subroutines - 1

Subroutines - 2

Subroutines - 3

TM Notation - 1

TM Notation - 2

TM Notation - 3

Multitape TMs

1-tape TM = Multitape TM - 1

1-tape TM = Multitape TM - 2

1-tape TM = Multitape TM - 3

1-tape TM = Multitape TM - 4

Thm 8.10 - run time of Thm 8.9

NTM - 1

NTM - 2

NTM - 3

NTM - 4

NTM - 5

TMs w/ Semi-infinite tapes - 1

TMs w/ Semi-infinite tapes - 2

Multistack machines - 1

Multistack machines - 2

Multistack machines - 3

Counter machines - 1

Counter machines - 2

Counter machines - 3

Counter machines - 4a

Counter machines - 4b

Counter machines - 4c

Counter machines - 4d

Counter machines - 4e

Counter machines - 5a

Counter machines - 5b

Counter machines - 5c

Counter machines - 5

Counter machines - 6

Counter machines - 7

Counter machines - 8

TMs & Computers - 1

TMs & Computers - 2

TMs & Computers - 3

TMs & Computers - 4

TMs & Computers - 5

TMs & Computers - 6

Running times - 1

Running times - 2

Running times - 3

Running times - 4

Running times - 5

Running times - 6

Copyright and IP Notice

Author: Dr. J

E-mail: Juliano@ecst.csuChico.edu

Homepage: http://www.ecst.csuchico.edu/~juliano

Further information:
Computer Science @ California State University, Chico

Best viewed with