A Turing machine (TM) is a tuple \(M=(Q, \Sigma, \delta)\) where \(Q\) is a finite set of states, containing a start state \(q_0\), an accepting state \(q_{y}\), and a rejecting state \(q_{n}\). The states \(q_{y}\) and \(q_{n}\) are distinct. \(\Sigma\)…