Chang et al noted that a hypothesis named for these things and formulated by Bennett and Gill violated a result about IP discovered by Shamir.  
Chang et al noted that a hypothesis named for these things and formulated by Bennett and Gill violated a result about IP discovered by Shamir.  A function with this name may do a pi radian rotation and is used to flip the sign of particular states in the first step of Grover's algorithm.  Two of these things, denoted A and B, exist such that PA ["P-A"] equals NPA ["N-P-A"] and PB ["P-B"] does not equal NPB ["N-P-B"] according to Baker-Gill-Solovay theorem, which thus implies no relativizing proof exists for the P versus NP problem. These constructs can be conceived of as (*) Turing machines with an additional head and semi-infinite tape that has an "ask" and "response" state. These constructs are not limited to solving decidable problems. For 10 points, name these theoretical black box constructs which are capable of giving a correct answer to any given instance of a decision or function problem. 
Chang et al noted that a hypothesis named for these things and formulated by Bennett and Gill violated a result about IP discovered by Shamir.  
oracle machine [or oracle function or random oracle or quantum oracle or oracle Turing machines; prompt on black-box function before mentioned; do NOT accept just "Turing machines"]