Definition 9.1 A Σ k -machine is an ATM such that on any input, every computation path can be divided into contiguous intervals such that (i) in any i
{"Image DocumentName": "Definition 9.1 A \u03a3k-machine is an ATM such that on any input, every computation path can be divided into contiguous intervals such that (i) in any interval, all configurations are either \u2228-configurations or all are \u2227-configurations; (ii) there are at most k intervals; and (iii) the first interval consists of \u2228-configurations.", "Image ImageDescription": "A \u03a0K -machine is similar, except we change (iii) to: (iii) the first interval consists of \u2227-configurations. A \u03a31-machine is just a nondeterministic TM. By convention, \u03a30-and \u03a00 - machines are deterministic TMs.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}