Question: Show that the language A = { 1> | the language accepted by the Turing Machine M 1 is 1 * } is not decidable.
Show that the language A = {

PROOF We let R be a TM that decides REGULARTm and construct TM S to decide ATM. Then S works in the following manner. S - "On input (M, w), where M is a TM and w is a string: 1. Construct the following TM M2 M2"On input: 1. If r has the form 0"1", accept. 2. If ar does not have this form, run M on input w and accept if M accepts w." 25 2. 3. Run R on input ?M-? If R accepts, accept; if R rejects, reject
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
