Computer Science 3331A/B Chapter Notes - Chapter 17: Nondeterminism, Readwrite, If And Only If
22 Jan 2020
School
Department
Course
Professor
Document Summary
Multiple tapes with own read/write head, less shifting required. K tape turing machine is a sixtuple, m = (k, ,r, ,s,h) A configuration of a k-tape machine m is a k+ 1 tuple (state,tape1,tape2 tapek) where each tape description is identical to the description before. If m halts, we define its output to be the contents of tape 1; contents of other tapes ignored. All other tapes will initially be blank with r/w head on some blank sq. At each step, m examines the square under each of its r/w heads. M can also stay put or move for its tapes, up arrow indicates no movement. K tape transition function for k tape machine ((k-h),r1 to (k,r1,{,^} Note that input is read on tape 1, the others are ignored. Theorum: let m be a k tape turing machine for some k >= 1, there is a standard tm m" where r is a subset r" and.
