Class Notes
(808,041)

Canada
(493,027)

Simon Fraser University
(12,062)

Cognitive Science
(80)

COGS 100
(67)

Michael Picard
(23)

Lecture

# An algorithm for effectively calculating a number.docx

Unlock Document

Simon Fraser University

Cognitive Science

COGS 100

Michael Picard

Fall

Description

An algorithm for effectively calculating a number-theoretic function is a
procedure that
a) can be specified in a finite number of steps
b) can be unambiguously followed by a human or mechanical
computer
c) will always yield an output for any input for which the function is
defined
(…)
Turing machine: Summary
- Idealized computing machines that can be specified purely
mathematically
- Do not have to take any particular physical form
- The machine table of a Turing machine is the program, specifying
what the appropriate output for a given input.
How it works
- Infinitely long tape divided into individual cells
- A finite alphabet of symbols, of which there must be exactly one in
each cell.
- A scanner/printer that can read what is in a given cell and write in it.
- The machine table of the Turing machine specifies instructions for
the scanner/printer.
- When the scanner/printer is in a given state it can
Move one cell to the L/R
Erase what is in a cell
Write a new symbol at a state
(…)
- The very same set of functions is calculable, however these
particulars are settled.
- The instructions specify what action to carry out given a) the internal
state of the machine, b) the input
- Each instruction has the same form Q*p, S*j, A, Q*t
Q*p – Internal state (…)
(…)
Sample program: example
Q1 0 R Q*

More
Less
Related notes for COGS 100