TIC 2151 - Theory of Computation: Decidability

TIC 2151 – Theory of
Computation
Lecture 9
Decidability
TIC 2151 – Theory of Computation

Lecture 09 - Outline
 Decidability – What is it?

 Undecidable problems: some examples.
 The Turing machine halting problem
2
Introduction
 “A Turning machine can do everything a real computer can do.”

 Church–Turing thesis states that a function on the natural numbers is
computable if and only if it is computable by a Turing machine.
TM Execution Possible Outcomes

Accept: Running TM M on input w eventually leads to qaccept.
Reject: Running TM M on input w eventually leads to qreject.
No Decision: Running TM M on input w runs forever, never reaches qaccept or
qreject.
3
Recognizing vs. Deciding
Turing-decidable: A language L is “Turing-decidable” if there exists a TM M

such that for all strings w:
– If w  L: eventually M enters qaccept.
– If w L: eventually M enters qreject
– also called a recursive language
4
Recognizing vs. Deciding
Turing-recognizable : A language L is “Turing recognizable” if there exists a

TM M such that for all strings w:
– If w  L: eventually M enters qaccept.
– If w  L: either M enters qreject or M never terminates.
– also called a recursively enumerable language
5
Decidability
Inside LTM:
Lde Lr.e. L
A language is Turing-recognizable or recursively enumerable if some Turing machine

recognizes it.
A language is Turing-decidable (decidable, or recursive) if some Turing machine decides it.
We call a language decidable if some Turing Machines decides it.

We call a language decidable if there is a Turing Machines saying Yes or No on every input.
Every decidable language is Turing-recognizable.
6
Decidability
Here the Turing Machine will either not stop or print

wrong results as their cannot be a program for the problem!
Inside LTM:
Lde Lr.e. L
Here the Turing Machine Here the Turing Machine

has to stop on every input has to stop on the input
and say Yes or No! only when saying Yes!
Decider vs. Recognizer?

Deciders always terminate.
Recognizers can run forever without deciding.
7
Decidability
Remember! Already inside

here it is difficult to
compute a result as
sometimes the machine runs
Lde Lr.e. L forever. But unfortunately

many real-world problems
are lying in this class.
Busy Beaver
~HALTING
Le
**
Lne = language not empty,
PCP
Le = language empty. HALTING
PCP = Post Correspondence Problem Lne
8
Decidability
Complete Summary:
Lfin  Lreg  LDPDA  Lcf  Lcs  Lde  Lre  L
9
Decidable Problem (example)
For example, the acceptance problem for DFAs of testing whether a particular DFA
accepts a given string can be expressed as a language, A DFA. This language contains the
encodings of all DFAs together with strings that the DFAs accept. Let
The problem of testing whether a DFA B accepts an input w is the same as the
problem of testing whether B,w. is a member of the language ADFA.
ADFA is a decidable language.
PROOF IDEA : We simply need to present a TM M that decides ADFA.
M = “On input B,w, where B is a DFA and w is a string:
1. Simulate B on input w.
2. If the simulation ends in an accept state, accept . If it ends in a
nonaccepting state, reject .”
B,w is a representation of a DFA B together with a string w. One reasonable
representation of B is simply a list of its five components: Q, , , q0, and F. M carries out
the simulation directly. It keeps track of B’s current state and B’s current position in the
input w by writing this information down on its tape. If the simulation ends in an accept
state, accept . If it ends in a nonaccepting state, reject 10
Undecidability
There is a specific problem that is algorithmically unsolvable. Computers appear to

be so powerful that you may believe that all problems will eventually yield to them.
The theorem presented here demonstrates that computers are limited in a
fundamental way.
you are given a computer program and a precise specification of what that
program is supposed to do (e.g., sort a list of numbers). You need to verify that the
program performs as specified (i.e., that it is correct).
The general problem of software verification is not solvable by computer.
The problem of determining whether a Turing machine accepts a given input string
we call it ATM by analogy with ADFA and ACFG. But, whereas ADFA and ACFG were
decidable, ATM is not.
ATM is Turing-undecidable language.

11
ATM is Turing-recognizable language
Undecidability
12
Undecidability
Halting problem. HALTTM, the problem of determining whether aTuring machine
halts (by accepting or rejecting) on a given input.
Is there an algorithm able to decide whether a given code will terminate?

In some programs it helps to look at some variables, in others look at the loops, or to
look at the recursive calls, or ... or ... (and here come infinitely many or’s)
Undecidabe languages examples
13
Learning Outcomes
Upon completion of this lecture, you should be able to:

 Explain the definition of Turing-decidable (recursive)
and Turing-recognizable (recursive enumerable)
languages.
 Tell that problems in Lr.e. and L are undecidable, but for
problems in Lr.e. we can give a TM program accepting
and stopping for at least all the Yes-instances.
 Name some problems from undecidable language (Lr.e.
and L).
14

TIC 2151 - Theory of Computation: Decidability

Uploaded by

Copyright:

Available Formats

TIC 2151 - Theory of Computation: Decidability

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TIC 2151 - Theory of Computation: Decidability

Uploaded by

Copyright:

Available Formats

TIC 2151 – Theory of

TIC 2151 – Theory of Computation

 Decidability – What is it?

 “A Turning machine can do everything a real computer can do.”

TM Execution Possible Outcomes

Turing-decidable: A language L is “Turing-decidable” if there exists a TM M

Turing-recognizable : A language L is “Turing recognizable” if there exists a

A language is Turing-recognizable or recursively enumerable if some Turing machine

We call a language decidable if some Turing Machines decides it.

Every decidable language is Turing-recognizable.

Here the Turing Machine will either not stop or print

Here the Turing Machine Here the Turing Machine

Decider vs. Recognizer?

Remember! Already inside

Lde Lr.e. L forever. But unfortunately

Lfin  Lreg  LDPDA  Lcf  Lcs  Lde  Lre  L

There is a specific problem that is algorithmically unsolvable. Computers appear to

ATM is Turing-undecidable language.

Is there an algorithm able to decide whether a given code will terminate?

Undecidabe languages examples

Upon completion of this lecture, you should be able to:

You might also like