CSCI 161 Chapter 3-4: TuringMachineNotes

• School: Santa Clara University
• Department: Computer Science
• Course: CSCI 161
• Professor: Sara Krehbiel

Document Summary

Tape ! infinite tape as a memory . + are head : rlw symbols & move around on the tape . can move both left & right special states for reject ravert occur immediately . a- alathur. Blank w is a special symbol uff a obj (cid:8869) used to fill infinite tape. D more exactly 1 cell either lett or resht. Note : if at leftmostend and want to more left , stay & don"t move your position . Don "t want to update ace rewrite same symbol. D final states ( 2 of them: accept. D computation : halt & accept, halt & reject. A turing machine ctm) is set of 7- tuples : Q is set of states blank symbol u eff. P fare alphabet where we t @eet" 8 transition function a xp qxpx { (cid:8869) r}