Describe a strategy you can use to decide whether m halts

Assignment Help Computer Engineering

Reference no: EM132141233

Question :

Suppose you are given a Turing machine M (not necessarily a decider), a string w, and a (different) magic genie.

You can ask the magic genie whether a certain Turing machine accepts a certain input string, and the genie will magically give you the correct yes/no answer.

You can ask the genie as many such questions as you like, about any Turing machine and any string.

Describe a strategy you can use to decide whether M halts on w. Remember to decide means to say with certainty that M halts on w or that M does not halt on w.

Note: Our magic genie decides AT M , an undecidable language. This genie really is magical.

Reference no: EM132141233

Questions Cloud

Determine the expected number of die rolls until a coin flip : Explain how to use die rolls to generate unbiased coin flips, and determine the expected number of die rolls until a coin flip is generated.

Write an algorithm to transfer all elements : Write an algorithm to transfer all elements from S to T so that the top of S is the first to be inserted onto T, and the bottom of S ends up at the top of T.

What was the human reason for encoding this information : What kind of encoding would this be and what was the human reason for encoding this information?

What would the value of the field containing the parity bits : Suppose the information content of a packet is the ASCII (8-bit code) representation of "OK" and an even parity scheme is being used.

Describe a strategy you can use to decide whether m halts : Suppose you are given a Turing machine M (not necessarily a decider), a string w, and a (different) magic genie.

What is the running time of insertion sort when it is used : Suppose that we are given an array A with n keys and k inversions. Here, an inversion is defined as a pair of entries that are out of order in the array.

Is the coin you flipped more likely to be the fair coin : Is the coin you flipped more likely to be the fair coin or the unfair one? Why?

What value of p gives you an expected value of your money : What value of p gives you an expected value of your money equal to its value before the play?

Write a python function to find a path between any two nodes : Write a Python function to find a path between any two nodes. Write code for a CGI script which asks the user to enter a length in inches.

User Account

All Pages