BU352 Study Guide - Final Guide: Halting Problem, Polynomial, Propositional Calculus
Document Summary
Lecture 23, 24: november 29 - december 2, 2016. De nition 23. 1 something is computable if it can be calculated by a systematic procedure. A decision problem is a problem which calls for an answer of either yes or no, on some input. A decision problem is decidable if there is an algorithm that, given an input to the problem: outputs yes if the input has answer yes , outputs no if the input has answer no . A problem is undecidable if it is not decidable. A reduction from problem a to problem b is an algorithm (or program) to solve problem a that relies on an algorithm (or program) to solve b. That"s all for fall 2016, hope these notes helped.
