0
votes
1answer
36 views

Multi-Tape Turing Machines to find palindrome

Given an Alphabet {a,b,c} , produce a Turing Machine which recognize if a given input string X is a palindrome. means if X is a palindrome, TM is halting and accepting, else halting and rejecting. ...
1
vote
1answer
35 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...