Computer Science 3331A/B Chapter Notes - Chapter 21: Subroutine, Ahold, Computable Function
22 Jan 2020
School
Department
Course
Professor
Document Summary
Note that we can describe a question as a language being in d or not, or as a problem where we ask is it decidable or not. Reduce a problem to one or more other problems when we describe a solution to the first problem in terms of solutions to the others. Example: we want to call jen but don"t have her number. We know that jm has it, so we reduce the problem of finding jen"s number to the problem of getting ahold of jim. The reduction exists and there is a procedure that works for getting hold of jim implies we will have jen"s number. Transformation must have the property that the answer to this new problem provides the answer to the original one. If theres no way to get hold of jim, doesn"t mean we can"t find jen"s number.
