Keeping in mind the capabilities of Turing machines and using the proper form for commands (ordered...

   

Transcribed Image Text:

Keeping in mind the capabilities of Turing machines and using the proper form for commands (ordered quintuples), give Turing-machine programs for each of the following items. Specifications: • Use the convention that the input n is always entered as a string of n + 1 consecutive 1s and that the read/write head starts at the leftmost 1. • Use go for the START state; use q100 for the HALT state. • Provide, separately from the list of quintuples, neatly-written documentation that tells the purpose of every state mentioned in your program. (a) Write a Turing-machine program for the function f given by f(n) n+1 for every natural number n. (b) Write a Turing-machine program that never halts-it just keeps executing commands but never reaches 100- regardless of what the input is. (c) Write a Turing machine program such that ⚫ if the input is 0 (a single "1" on the tape), then the output is also (), but ⚫if the input is not 0, then the program does not halt (it just keeps executing commands but never reaches 9100). Keeping in mind the capabilities of Turing machines and using the proper form for commands (ordered quintuples), give Turing-machine programs for each of the following items. Specifications: • Use the convention that the input n is always entered as a string of n + 1 consecutive 1s and that the read/write head starts at the leftmost 1. • Use go for the START state; use q100 for the HALT state. • Provide, separately from the list of quintuples, neatly-written documentation that tells the purpose of every state mentioned in your program. (a) Write a Turing-machine program for the function f given by f(n) n+1 for every natural number n. (b) Write a Turing-machine program that never halts-it just keeps executing commands but never reaches 100- regardless of what the input is. (c) Write a Turing machine program such that ⚫ if the input is 0 (a single "1" on the tape), then the output is also (), but ⚫if the input is not 0, then the program does not halt (it just keeps executing commands but never reaches 9100).

Answer rating: 100% (QA)

Turing Machine Programs a Turingmachine program for the function fn n 1 States q0 Initial state q1 M... View the full answer