Questions refer to the following variant of Turing machines. A linear bounded automaton (LBA) is like an ordinary one-tape Turing machine, except for the fol lowing modification: its tape alphabet contains an extra distinguished symbol - the night endmarker, and the machine is constrained never to move to the right of the right endmarker nor overwrite it with a different symbol. The input string is initially enclosed between the left and right endmarkers with no blank cells, and the machine starts in its start states scanning the left endmarker ; that is, the start configuration on input res is (s, 30). 1. State formally in terms of the transition function 6: Qr+Qxrx (L, R) what it means to say, "The machine is constrained never to move to the right of the right endmarker nor overwrite it with a different symbol." Take care to use proper quantification E, M) in your formal statement.
2. Prove that the halting problem for LBAS is decidable.
3. Prove that it is undecidable whether a given LBA runs in polynomial time. (Hint. Encode the halting problem for arbitrary Turing machines Given Me, build an LBA with M and encoded in its finite control. On any input the LBA ce its input and do something interesting with Afand).