Problem 6 In This Problem We Explore The Notion Of Oracle Reducibility If A Is A Language Then A Turing Machine With 1 (9.84 KiB) Viewed 31 times
Problem 6 In this problem, we explore the notion of oracle reducibility. If A is a language, then a Turing machine with oracle A is a Turing machine with a "magical" subroutine that decides a
membership in A. In other words, the subroutine, when given a string w, tells the machine whether or not w E A. Let HALTIM = {{M,r) | M is a Turing machine that halts on x} Show that there is a Turing machine with oracle HALTTM that decides the following problem with only two questions to the oracle: Given three (machine, input) pairs (M1,11), (M2, 12), (M3, 13), decide for each pair whether the Turing machine halts on the corresponding input. Note: This is trivial if one allows three questions. Just ask the oracle whether (M;,ti) HALTTM for i = 1,2,3.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!