**Turing Machines – Decidability**Lecture 25 Section 3.1 Fri, Oct 19, 2007**Turing Machine as Calculator**• Design a Turing Machine that will compare (<) two integers. • Input: 0110#11100 • Output: 1 (true) • Input: 11100#0110 • Output: 0 (false)**Turing Machine as Calculator**• Design a Turing Machine that will add two integers. • Input: 0110#11100 • Output: 100010**Turing Machine as Calculator**• Design a Turing Machine that will multiply two integers. • Input: 0110#11100 • Output: 10101000**Turing Machine as Calculator**• Design a Turing Machine that will find the square root of an integer. • Input: 11100 • Output: 101**Configurations**• The current “state” of a Turing machine is fully described by specifying • The current state, • The current tape position, • The current tape contents.**Configurations**• This can be summarized in a triple uqv, called a configuration, where u, v * and qQ. • The interpretation is • The current state is q. • The current tape content is uv. • The current tape position is at the first symbol in v.**Computations**• We say that a configuration C1yields a configuration C2 if there is a transition that takes the Turing machine from C1 to C2. • A computation is a sequence of configurations C1, …, Cn, where Ci yields Ci + 1 for i = 1, …, n – 1.**Example**• Our machine that accepts {w#w} will perform the following computation on input 101#101: • q0101#101 • $q301#101 • $0q31#101 • $01q3#101 • $01#q4101**Example**• $01q5#$01 • $0q61#$01 • $q601#$01 • q6$01#$01 • $q001#$01 • $$q11#$01 • etc.**Accepting and Rejecting Configurations**• The start configuration on input w is q0w. • An accepting configuration is one where the state is qaccept. • A rejecting configuration is one where the state is qreject.**Accepting Input**• A Turing Machine accepts input w if there is a computation C1, …, Cn, where • C1 is the start configuration on w. • Cn is an accepting configuration.**Rejecting Input**• A Turing Machine rejects input w if there is a computation C1, …, Cn, where • C1 is the start configuration on w. • Cn is a rejecting configuration.**The Third Possibility**• It is possible that a Turing Machine neither accepts nor rejects an input w.**Turing-Recognizable Languages**• The language of a Turing machineM is the set of input strings that are accepted by M. L(M) = {w | M accepts w}. • A language is Turing-recognizable if it is accepted by some Turing machine.**Turing-Decidable Languages**• A Turing Machine is a decider if it halts on all inputs. • A Turing machine Mdecides a language L if M accepts every string in L and rejects every string not in L. • A language is Turing-decidable if it is decided by some Turing machine.**Example**• The language {w#w | w *} is a Turing-decidable language. • Every Turing-decidable language is Turing-recognizable, but not every Turing-recognizable language is Turing-decidable.