Question: Let L 1 = { M | M is a Turing machine that accepts the string 1 } . I.e . , if the language
Let LM M is a Turing machine that accepts the string
I.e if the language accepted by M contains the string possibly along with other strings
then M in L
Define the function f M WM as follows, where W denotes the input to M:
If M W is not a valid encoding of a Turing machine M and an input string W
then make M reject.
If M W is a valid encoding, then make M simulate M on input W using a
universal Turing machine modified such that if M accepts W or M rejects W then
M accepts W
That is f M W returns the encoding of a universal Turing machine M where M
simulates the execution of M on the input W and accepts if M accepts or rejects W
Give a brief argument to prove or disprove the following proposition:
f is computable.
Give a formal argument to prove or disprove the following proposition:
M WM W in HALTT M f M W in L
Give a formal argument to prove or disprove the following proposition:
M WM W in HALTT M f M W in L
Give a brief argument to prove or disprove the following proposition:
L
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
