Class Notes (808,041)
Canada (493,027)
COGS 100 (67)

An algorithm for effectively calculating a number.docx

2 Pages
Unlock Document

Simon Fraser University
Cognitive Science
COGS 100
Michael Picard

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

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.