Snivelling Sam the Shonky Snake Oil Salesman has heard about your work on Turing machines. This...

  

Transcribed Image Text:

Snivelling Sam the Shonky Snake Oil Salesman has heard about your work on Turing machines. This is of great interest to Sam, who wishes to set up a Gallery of Important Turing Machines which are Useful and Brilliant (GITMUB). This will showcase various Turing machines, which must be of the acceptor/rejector type (i.e. Turing machines which accept a given language by terminating in an accepting state). Sam is keen to ensure that he only has the "best and brightest" Turing machines on display from those submitted to GITMUB by the general public, and so insists on the following policy on adding machines. Let the machine to be added to GITMUB be M, and the machines already in GITMUB be M₁,..., Mn. If L(M) ‡ L(M;) for all 1 ≤ i ≤n, then M is added to GITMUB. Otherwise, (i.e. L(M) L(M) for some 1 ≤ i ≤n) then Sam makes = a choice between M and M₁, and either rejects M as a member of GITMUB, or ejects M; from GITMUB and replaces it with M (according to what he perceives as the 'inherent artistic merit' of each machine). This means that Sam can boast that GITMUB's machines are all guaranteed to be unique representatives of machines accepting a particular language. Explain why, under the above policy, GITMUB can never be guaranteed to contain more than one machine. Snivelling Sam the Shonky Snake Oil Salesman has heard about your work on Turing machines. This is of great interest to Sam, who wishes to set up a Gallery of Important Turing Machines which are Useful and Brilliant (GITMUB). This will showcase various Turing machines, which must be of the acceptor/rejector type (i.e. Turing machines which accept a given language by terminating in an accepting state). Sam is keen to ensure that he only has the "best and brightest" Turing machines on display from those submitted to GITMUB by the general public, and so insists on the following policy on adding machines. Let the machine to be added to GITMUB be M, and the machines already in GITMUB be M₁,..., Mn. If L(M) ‡ L(M;) for all 1 ≤ i ≤n, then M is added to GITMUB. Otherwise, (i.e. L(M) L(M) for some 1 ≤ i ≤n) then Sam makes = a choice between M and M₁, and either rejects M as a member of GITMUB, or ejects M; from GITMUB and replaces it with M (according to what he perceives as the 'inherent artistic merit' of each machine). This means that Sam can boast that GITMUB's machines are all guaranteed to be unique representatives of machines accepting a particular language. Explain why, under the above policy, GITMUB can never be guaranteed to contain more than one machine.

Answer rating: 100% (QA)

Under the above policy GITMUB can never be guaranteed to contain more than one machine because of th... View the full answer