M269 Lec 11 Algorithms, Data Structures, and Computability PDF

M269 Algorithms, Data Structures and Computability BY: DR. AHMED GAWISH [email protected]  Agenda 1] Prepositional Logic and Predicate Logic. 2] Turing Machine 3] Computability and Limits of Computation  Logic in Computer Science Logic has a...

M269 Algorithms, Data Structures and Computability BY: DR. AHMED GAWISH [email protected]  Agenda 1] Prepositional Logic and Predicate Logic. 2] Turing Machine 3] Computability and Limits of Computation  Logic in Computer Science Logic has a profound impact on computer-science. Some examples: Propositional logic – the foundation of computers and circuitry Databases – query languages Programming languages (e.g. prolog) Propositional Logic Design Validation and verification First Order Logic AI (e.g. inference systems) Higher Order Logic... Temporal Logic 3  Propositional logic: Syntax A proposition – a sentence that can be either true or false. The symbols of the language: Propositional symbols (Prop): A, B, C,… Connectives In propositional logic generally we use five connectives which are − o OR (∨) o AND (∧) o Negation/ NOT (¬) o Implication / if-then (→) o If and only if (⇔). 4 OR (∨) − The OR operation of two AND (∧) − The AND operation of two propositions A and B (written as A∨B) is propositions A and B (written as A∧B) is true if at least any of the propositional true if both the propositional variable A variable A or B is true. and B is true. Negation (¬) − The negation of a Implication / if-then (→) − An proposition A (written as ¬A) is false when implication A→B is the proposition “if A, A is true and is true when A is false. then B”. It is false if A is true and B is false. The rest cases are true. If and only if (⇔) − A⇔B is bi-conditional logical connective which is true when p and q are same, i.e. both are false or both are true. First Order Logic To understand the predicate logic, please see the following video:  Introduction to Turing Machines Before going into this topic, please see the following videos: idea Intro: https://www.youtube.com/watch?v=cDc6Gfo3egk Idea: https://www.youtube.com/watch?v=-ZS_zFg4w5k 0 0 1 1 10 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0  The Turing Machine 10 01 1 10 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 A TM consists of an infinite length tape, on which input is provided as a finite sequence of symbols. A head reads the input tape. The TM starts at start state s0. On reading an input symbol it optionally replaces it with another symbol, changes its internal state and moves one cell to the right or left.  The Turing Machine A TM is defined as: TM = where, S is a set of TM states T is a set of tape symbols s0 is the start state HS is a set of halting states  : S x T →S x T x {L,R} is the transition function  Simple TM Examples Turing Machine U+1: Given a string of 1s on a tape (followed by an infinite number of 0s), add one more 1 at the end of the string. #111100000000……. ➔ #1111100000000……….  Simple TM Examples TM: U+1 (s0, 1) |-- (s0, 1, R) (s0, 0) |-- (h, 1, STOP) #s0111100000….. → #1s011100000….. → #11s01100000….. → #111s0100000….. → #1111s000000….. → #11111h0000….. STOP  Exercice state symbol Δ(state, Solution symbol) S0 b (halt, a, stop) s0 “ aaaabb” S0 a (S1 , a, right ) s1 “ aaaabb ” S1 b (halt, b, stop) s0 “ aaaabb ” S1 a (S0 , a, right ) s1 “ aaaabb ” s1 “ aaaabb ” Input = “aaaabb” halt “ aaaaab ” What is the output for this input? Input = a finite sequence of “a” symbol, followed by an infinite sequence of “b”. Describe what the output this machine generates.  Turing’s Thesis Any mathematical problem solving that can be described by a mechanical procedure (algorithm) can be modeled by a Turing machine. All computers today perform only mechanical problem solving. They are no more expressive than a Turing machine.  Halting Problem The Halting problem Given a program and an input to the program, determine if the given program will eventually stop with this particular input. If the program doesn’t stop, then it is in an infinite loop and this problem is unsolvable 22  Turing’s Thesis Turing’s thesis is not a “theorem” there is no “proof” for the thesis. The theorem may be refuted by showing at least one task that is performed by a digital computer which cannot be performed by a Turing machine. Many contentions have been made to this end. However, till date there have not been any conclusive evidence to refute Turing’s thesis.  The Turing Machine Conclusions Turing machines are a minimal extension over PDAs which provide greater expressiveness. TMs are at a level that is much below the assembly language of any typical microprocessor. So in the practical world, TMs are more useful in what they cannot do rather than in what they can.  Computability and Limits of Computation Examples of Limitations: Limits on Arithmetic Limits on Components Limits on Communications 25  Limits on Arithmetic There are limitations imposed by the hardware on the representations of both integer numbers and real numbers. The maximum number of significant digits that can be represented is limited to a certain value. Significant digits Those digits that begin with the first nonzero digit on the left and end with the last nonzero digit on the right  Limits on Components Although most errors are caused by software, hardware components do fail Limits on Communications Error-detecting codes Techniques to determine if an error has occurred during the transmission of data and then alert the system Error-correcting codes Error-detecting codes that detect an error has occurred and try to 27 determine the correct value  Limits of Software Commercial software contains errors Software testing can demonstrate the presence of bugs but cannot demonstrate their absence As we find problems and fix them, we raise our confidence that the software performs as it should But we can never guarantee that all bugs have been removed 28 Thank You