COMS W1004 Lecture Notes - Lecture 22: Finite Set, Problem Set

• School: Columbia University
• Department: Computer Science
• Course: COMS W1004
• Professor: Adam Cannon

Document Summary

For programming project 5 due tuesday 4/19, create your own tester to test your code and submit it along with main code. Mathematical concept of computation and algorithms: model of computation, problems: symbolic manipulation problem, building the model. Turing machine ingredients: finite set of symbols. {0,1} (include b=blank: finite set of states. Infinite tape made of cells which hold a single symbol: set of instructions (finite) Turing machine instructions: 5-tuple ( _ , _ , _ , _ , _ ) (current state, current symbol, next symbol, next state, direction) Turning machine rules: tape beings with finite set of non-blank symbols, start at left-most non--blank, start in state 1, stop when no appropriate instruction. Example 1: = 0,1, s = {1,2} b b. Start at left most non-blank, which is highlighted 1 (1,1,0,1,r) When at state 1, looking at 1, replace with 0, stay in state 1, move to the right b b.