COGS 100 Lecture Notes - Turing Machine

22 views2 pages
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*
2
Q2
1
0
Q*
1
Q3
0
1
Q*
3
Q4
1
R
Q*
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.