Chapter 2

Computability
Procedure:
• A procedure for solving a problem is a finite sequence of instructions
which can be mechanically carried out given any input.

Effective Procedure
• Finitely describable
• Well defined, discrete steps
• Always terminates

• Algorithm

• Al algorithm is a procedure that terminates after a finite number of

steps.
Limitations of computer science
Major reasons useful calculations cannot be done:
• Execution time of program is too long
• problem can take years or centuries to finish
• Problem is not computable
• no computer program can solve the problem
• We do not know how to write a program to solve the problem
• problems that can conceivably be solved
• includes many problems in artificial intelligence and computer
vision, such as understanding language, object recognition,
tracking, prediction
What problems can be solved by computers?
• Equivalent to: “What decision problems can be solved?”

• Decision problem
• problem where the answer is always YES/NO

• Arbitrary problem can always be reduced to a decision problem

• There are decision problems for which algorithms do not exist

• there are more different decision problems than there are different programs
• if there are more decision problems than programs, then it must be the case
that some decision problems cannot be solved by programs
Function evaluation
• A decision problem is a question with a YES/NO answer:
• Is 613511 a prime number?
• Is my birthday on a Sunday next year?
• Did I pass the CPS1 final exam?
• Sometimes a particular answer from a set of possible solutions is required
• What is the smallest prime factor of 613511?
• On what day of the week is my birthday next year?
• What grade will I get on the CPS1 final exam?
• The process of answering questions where a particular answer is uniquely
determined from the given information can be viewed as the evaluation of a
function
Functions
• A function is a correspondence between a collection of possible input
values and a collection of output values such that each possible input
is assigned a unique output
• Example: the addition function
• inputs are value pairs, outputs are values representing the sum of each input
pair
• output is unique, exactly one value for each input pair
• Process of determining output for given input is called computing or
evaluating the function
• The ability to evaluate functions gives us the ability to solve problems
• to solve the addition problem we must evaluate the addition function
Computable functions
• Algorithms are the means by which we formally express the evaluation of a
function
• Can we design algorithms to evaluate all functions?
• No!
• Exist functions so complex that there is no well-defined step-by-step process
for determining their output based on their input values
• The evaluation of these functions lies beyond the capabilities of any
algorithmic system
• These functions are said to be noncomputable
• Functions whose output values can be determined algorithmically from their
input values are said to be computable
• functions having an algorithm that solves them
• Computability refers to the ability of a problem or function to be solved or
computed by an algorithm, typically modeled by a theoretical computing
device like a Turing machine

• A problem is considered computable (or decidable) if there exists an algorithm

that can take any valid input for the problem and, after a finite amount of time,
produce a correct output—either a solution or a definitive "yes" or "no" answer
in the case of decision problems.
Definition:
• A function f:Σ∗→Σ∗ (where Σ∗ is the set of all finite strings over some
alphabet Σ) is computable if there exists a Turing machine M that, given
any input x , halts and outputs f(x) f. For decision problems, a language
L⊆Σ∗ is computable if there is a Turing machine that halts on every input
x and accepts if x∈L and rejects if x∉L.

• Definition: A function f(x) is computable if a Turing machine can output

f(x) f for any input x and halt.
Limitations of machines
• Machines can only perform computations described by algorithms
• the study of computable functions is the study of the ultimate capabilities of
machines
• If we can build a machine with the capabilities to evaluate the entire set of
computable functions, then the machines we build are as powerful as we can
make them
• On the other hand …
• if we discover that the solutions to a problem requires the evaluation of a
noncomputable function, we know the solution to that problem lies beyond
the capabilities of machines
Is a problem computable?
• Suppose we create a list of all programs for evaluating computable problems

• To ask whether a problem is computable is to ask if there is a program in the

list to solve the problem

• This is not the same as actually identifying the program in the list that solves
the problem

• There are many computable problems whose solutions have not yet been
identified
Computing Functions with Turing Machines
A function may have many parameters:

Example: Addition function

f (x, y) = x + y
Turing computable

• Functions that can be computed by a Turing machine are said

to be Turing computable
Turing-computable
• A function is computable if it can be computed by a Turing machine
• or, a function is computable if a program exists that can compute it
• or, a function is computable if there is an effective algorithm for evaluating the
function which, given any input values for which the function is defined, produces the
correct result and halts in a finite amount of time

• Q: Is there anything a Turing machine cannot do?

• A: Yes!
Turing Machine Pseudocode for f (x) = 2x

1. Replace every 1 with $

2. Repeat:
3. Find rightmost $, replace it with 1
4. Go to right end, insert 1
5. Until no more $ remain
Turing Machine Pseudo code:
• Repeat
Match a 1 from x with a 1 from y

Until all of x or y is matched

• If a 1 from is x not matched
erase the tape, write 1 (X>y)
else
erase tape, write 0 (x <= y)
Definition of Algorithm:

An algorithm for function f(w) is a Turing Machine which computes f (w)

Algorithms are Turing Machines

When we say:
There exists an algorithm

We mean:
There exists a Turing Machine that executes the algorithm
Exercise : Show that f(x)=x+1 is computable.
Noncomputability

• A function is noncomputable if there exists no Turing machine that could

compute it

• or, a noncomputable function is any function that cannot be computed by any

program
• many more functions than there are programs
• not possible to have a program for every function
A noncomputable problem
• Problem: List all subroutines that input an integer and return an integer
• here is one short subroutine:
int sub1(int x)
{
return 1;
}
• and here is another:
int sub2(int x)
{
return 2;
}
• Can make infinitely many such subroutines
Halting
int programA( int x ) int programB( int x )
{ {
while( x == x ) while( x > 10 )
x = x; x = x;
return x; return x;
} }

• Programs that run forever do not halt

• programA
• programs with infinite loops
• Programs may halt on some inputs but not on others
• programB
• Programs with no loops always halt
• programs composed of assignment statements, if statements and the return statement
Halt or not?
• Will the following code eventually terminate?
while(x > 1)
{
if(x > 2)
x = x - 2;
else
x = x + 2;
}
• What if x is 8? How about 9?
Halt or not?
• Will the following code eventually terminate?

while(x > 1)
{
if( x % 2 == 0)
x = x / 2;
else
x = 3*x + 1;
}

• What if x is 8? How about 7? How about any number > 0?

The halting problem
• Q: Is it possible to write a Java program to answer the following
question
Does a given program halt on all inputs?
• It would be useful if we could write a program or compiler to test
if a given source program contains an infinite loop
• If we had such a program, start
then we would never
execute a program
with an infinite loop does this no
program halt?
• This problem is known
halt
as the halting problem yes
Given a program and an input, can we determine
whether the program will eventually stop (halt) or run
forever?

Can we build one universal algorithm that can look at any

program and input and always correctly answer:
“Yes, it halts” or
“No, it runs forever”?

32
The halting problem is noncomputable
No finite program can be written that will check other
programs and halt in a finite time giving a solution to the
halting problem

• There is no single finite program that will answer the halting question
for all programs
start

does this no
program halt?

halt
yes
 Proof by contradiction
• How did Turing prove that such a program is theoretically impossible?

• Proof by contradiction:
• Assume there is an algorithm DoesHalt(P,I) that returns “yes” if program P halts
when given input I and “no” otherwise
• Show that this assumption leads to a contradictory situation
• Conclude that our initial assumption – the existence of a program to tell if another
program halts – must be false
Formally, the Halting Problem asks:

Given a description of a program P (e.g., a Turing machine) and an

input I, can we construct a universal algorithm H that takes P and I
as inputs and correctly outputs:

"Yes" if P halts on I, or
"No" if P runs forever on I?
Proof by Contradiction
1. Assume there exists an algorithm H(P,I) that solves the Halting Problem.
• That is, H takes a program P and input I and returns "halt" or "not halt"
accurately.
i.e
H(P,I) // input program p and input I
halt //return halt if p halts on input I
or not halt
2. Now, let’s construct a new program C that uses H as a subroutine:
C(X) //C takes a Program X as input
if(H(X,X)==halt)
Loop forever
else return
3. Now, run C(C) on itself.

i.e
C(C):
• If H(C,C) says C halts on C, then C(C)loops forever
(contradicting the prediction that it halts).

• If H(C,C) says C does not halt on C, then C(C)) halts (again, a

contradiction).
Programs that read programs
Program input output
Program

• Almost every problem related to the behavior of programs is noncomputable

• programs to check for property X in the behavior of all other programs
• halting, equivalence, printing, correctness

• We can write programs to check almost any syntactic feature of programs

• a compiler is a program that reads programs
• we can measure the length of programs, number of statements, characters, arithmetic
expressions
Computable or noncomputable?
1. Write a program that inputs a sequence of characters and returns true if it is a
legal Java program

Algorithm

1. Take any finite sequence of characters as input.

2. Output "true" if the sequence is a syntactically valid Java program, and "false" otherwise.
3. Always halt with a correct answer in finite time.

Yes, the problem is computable. There exists an algorithm that can take any
sequence of characters and determine in finite time whether it is a legal Java
program based on syntax.
Java compiler (lexer and parser) does this
Computable or noncomputable?
2. Write a program that inputs a sequence of characters and returns true
if any permutation of these characters is a legal Java program

To determine computability, we need an algorithm that:

1. Generates all permutations of the input string.

2. Checks each permutation to see if it’s a syntactically valid Java program.
3. Returns "true" if at least one permutation passes, "false" if none do.
Halts for every possible input.
Since there are finitely many permutations and checking each one is
computable, we can:

1. Enumerate all permutations.

2. Run the Java syntax checker on each.
3. Stop and return "true" as soon as one permutation is valid, or return
"false" after exhausting all permutations with no success.

This process terminates because the number of permutations is finite and

each check is finite.

So, the problem is computable

Computable or noncomputable?
3. Write a program that inputs a program in any programming

language and returns true if the characters can be rearranged to form

a legal Java program
4. Write a program that inputs a Java program and returns true if the program
computes the sum of its inputs

5. Write a program that inputs two Java programs and returns true if both
programs always produce the same output
Computable or noncomputable?
1. Computable

2. Computable

3. Computable

4. Noncomputable

5. Noncomputable
 Recursively Enumerable Languages
 Recursive Language (REC)

Recursively Enumerable (RE)

• A recursively enumerable language (also called a semi-decidable or Turing-recognizable
language

• It describes a class of formal languages that can be recognized—or partially decided—by a

computational model, but not necessarily fully decided.
• Definition
• A language L (a set of strings over some alphabet) is recursively enumerable if there exists
a Turing machine M such that:
• For any string w in L (i.e., w∈L), M halts and accepts w .
• For any string w not in L (i.e., w∉L), M either rejects w by halting or runs forever
without halting.
Recursive Enumerable (RE)…

• In other words:
• If a string belongs to the language, the Turing machine will confirm it by
halting in an accepting state.
• If a string doesn’t belong, the machine might halt and reject, or it might loop
indefinitely—we’re not guaranteed a definitive "no" answer
Recursive Enumerable (RE)…

• Partial Decidability: A recursively enumerable language is "semi-decidable."

You can build a machine to say "yes" when a string is in the language, but you
can’t always trust it to say "no" definitively for strings not in the language.

• The Turing machine acts like an enumerator or recognizer. It can list out
(enumerate) all strings in the language over time or recognize them when
presented as input.
Recursive Enumerable (RE)…

• A TM may divide all strings on Σ* into 3 states:

• All accepted states
• All strings on which TM rejects
• All strings on which TM loops
Recursive Language (REC)
• A recursive language (subset of RE) can be decided by Turing machine,
which means it will enter into final state for the strings of language and
rejecting state for the strings which are not part of the language.

• If L is a recursive language, there is a TM M such that:

• if w ∈ L , then M halts in a final (or accept) state

• if w ∉ L , then M halts in a non final (or non accept) state

e.g.;
L= {anbncn|n>=1} is recursive because we can construct a turing
machine which will move to final state if the string is of the form
anbncn else move to non-final state.
 Recursive Language (REC)
So the TM will always halt in this case. REC languages are also called as Turing
decidable languages. The relationship between RE and REC languages can be shown in

The set of Recursive

languages is the subset of all
RE.
Closure Properties of Recursive Languages

TM Block Diagrams

If L is a recursive language, then a TM M that accepts L and always halts

can be pictorially represented by a “box” that has one input and two
outputs.

Yes
W M
No
Closure Properties of Recursive Languages

If L is a recursively enumerable language, then a TM M that accepts L cab

be represented by a “box” that has one input and one outputs.

W M Yes
Complement
Theorem: The recursive languages are closed with respect to
complementation.
• That is, if L is RL, then so L’
L’ = Σ* - L
L’ = {w∣w∈L}
Proof: Let M be a TM such that L=L(M) and M always halts.
Construct TM M’ as follows: M’

W yes
M W yes
no M
no
Note: M’ accepts iff M does not
M’ always halts since M always halts
From this, it follows that the complement of L is recursive.
Construction of a M’ for L’
We construct a new Turing machine M′ as follows:

Algorithm for M′:

On input w:
[Link] M(w)
[Link] M accepts, then Reject
[Link] M rejects, then Accept
Why This Works:
Since M halts on every input′ also halts on every input
Behavior:
If w∈L, then M accepts ⇒ M′ rejects ⇒ w∉L’,
If w∉L’ then M rejects ⇒ M′ accepts ⇒ w∈L’
54
Closure Properties of Recursive Languages

Theorem Union:

If L1 and If L2 are two recursive languages, their union L1∪L2 will also be recursive.

Proof:
Since L1 and L2 are recursive languages,

. yes
yes
M1 M2
no
W W no
Construction Turing Machine M for L1∪L2

Why This Works

We build a new Turing machine M as follows: If w∈L1 ​:
Algorithm for M: M1​ accepts ⇒ M accepts
If w∈L2​:
On input w : M1​ rejects, but M2​ accepts ⇒ M accepts
1. Run M1(w)
If w∉L1∪L2w :
​ If M1 accepts, accept Both reject ⇒ M rejects
2. Otherwise, run M2(w)
​If M ​ accepts, Accept Halting Guarantee
M1 halts on all inputs
Else Reject M2 halts on all inputs
Therefore, M always halts
56
• Let M1 and M2 be TMs such that L1=L(M1) and L2=L(M2) and M1 and M2 always halt.
Construct TM M as follows:
• M first simulates M1. If M1 accepts a string w, then M also accepts the string w.
• If M1 rejects a string w then M’ simulates M2 accepts the string w if M2 accepts it and
rejects the string w if M2 rejects it.

yes

No
w yes
No

Note that: L(M)= L(M1) U L(M2)

M always halts since M1 and M2 always halt.
Intersection

If L1 and If L2 are two recursive languages, their intersection L1 ∩ L2 will also

be recursive.

Show that L =L1 ​∩L2 ​is recursive

Construction
Build a machine M:
Algorithm: On input w:
1. Run M1(w)
If it rejects ⇒ Reject
2. Run M2(w)
If it accepts ⇒ Accept
Else ⇒ Reject
Intersection/Recursive –

Accept
M1
Reject
AND Accept
Input w M

Accept
M2 OR Reject
Reject

59
Intersection

For Example:

L1= {anbncndm | n>=0 and m>=0}

L2= {anbncndn | n>=0 and m>=0}

L3=L1 ∩ L2
= { anbncndn | n>=0} will be recursive.
Concatenation
Theorem :If L1 and L2 are recursive languages, then so is L1L2.
Prove L=L1⋅L2​={w∣w=xy,x∈L1​,y∈L2​} is recursive.
Proof:
Let M1 and M2 be Turing machines such that
L(M1) = L1 and L(M2) = L2

A split of an input w is a pair (x,y) such that w = xy.

We call the split good if M1 accepts x and M2 accepts y
Create a Turing machine M that :
• computes all splits of the input w
• checks all splits in parallel whether they are good
• accepts the input w as soon as a good split is found

• Then L(M) = L1L2

Key Idea
For a string w,
try all possible splits:
w=xy
Then:
check if x∈L1 ​ using M1
check if y∈L2 ​ using M2

If any split works → accept

62
For Example:

L1= { anbncn| n>=0 }

L2= { dmemfm | m>=0 }
L3= L1.L2 = { anbncndm emfm | m>=0 and n>=0} is also recursive.
Kleene Closure: If L is recursive, its kleene closure L* will also be recursive.

Given: Let L be a recursive language.

Then there exists a decider M such that:
M halts on every input, and decides membership in L

To Prove:
L∗={ w∣w=x1x2⋯xk, k≥0, xi∈L } is recursive.
Key Idea
A string w∈L∗ if it can be split into zero or more substrings, each in L.
So we:
• try all possible ways to partition w, and
• check each piece using the decider M

65
Build a Turing machine M′:
Algorithm: On input w of length n:
1. Special case:
If w=ϵ⇒ Accept (since ϵ∈L∗)
2. Generate all possible ways to split w into substrings:
w=x1x2⋯xk
3. For each partition:
• For every substring xi, run M(xi)
4. If all substrings in any partition are accepted ⇒ Accept
5. If no partition works ⇒ Reject

66
For Example:
L= {anbncn |n>=0}
L*= ={anbncn | n>=0 } * is also recursive.

67
Closure Properties of Recursively Enumerable
Languages

• If L, L1 and L2 are recursively enumerable languages, then so

are
• L1 ∪ L2,
• L1L2,
• L∗
And
• L1 ∩ L2

• Recursively enumerable languages are not closed under

complement
Closure Properties of Recursively Enumerable Languages

Theorem: If L1 and L2 are recursively enumerable languages, then so is L1 U

L2

Proof:

w M1 Yes if w ∈ L1

w M2 Yes if w ∈ L2
Given
Let L1 and L2 be recursively enumerable languages.

Then there exist Turing machines:

• M1​ that recognizes L1
• M2 that recognizes L2
Meaning:
• If w∈Li ​, Mi accepts
• If w∉Li ​, Mi may reject or loop forever
70
o Prove L=L1∪L2 ​is recursively enumerable.

• Unlike recursive languages:M1​, M2 may not halt

• So we cannot run them sequentially (one after the other),
because one might loop forever.

Parallel Simulation
We simulate both machines step by step in parallel.

71
Construction (Recognizer for Union)

• Build a Turing machine M:

Algorithm: On input w:
[Link] M1(w) and M2(w) in parallel:
Step 1 of M1 ​, Step 1 of M2
Step 2 of M1 ​, Step 2 of M2
Step 3 of M1 ​, Step 3 of M2 ​, and so on...
[Link] either machine accepts, Accept
72
Construct a TM M such that when any of M1or M2 accepts, M
accepts.

Clearly, M halts M
when input w
Accept
belongs to L1 U M1
L2. Accept
L(M)=L1UL2
Input w M

Hence,L1 U L2 is Accept
recursive. M2

73
Theorem: Recursively enumerable (RE) languages are closed
under intersection.
Given:
Let L1 ​ and L2​ be recursively enumerable languages.
Then there exist Turing machines:
M1 ​ recognizing L1
M2​ recognizing L2
Meaning:
If w∈Li ​, Mi accepts
If w∉Liw, Mi ​ may reject or loop forever
74
o Prove
L=L1∩L2 ​is recursively enumerable.
Construction (Recognizer for Intersection)
Build a Turing machine M:
Algorithm:
On input w:
1. Simulate M1(w) and M2​(w) in parallel :
• Step 1 of M1​, Step 1 of M2
• Step 2 of M1​, Step 2 of M2
• Step 3 of both, and so on...
2. Keep track of whether:
M1 ​ has accepted
M2 has accepted 3. If both have accepted, 👉 Accept 75
Theorem : If L and L’ are both recursively enumerable Languages, the L(and
therefore L’) is recursive.

• Proof:
Let M1 be a TM such that L(M1)=L and M2 be a TM such that L(M2)=L’.

w M1 Yes if w ∈ L w M2
Yes if
w ∈ L’
Construct a TM M such that
when M1 accepts, M accepts
When M2 accepts, M rejects

Clearly, M halts M
since for any given Yes Yes
string either M1
M1
halts or M2 halts‘.

Input w
Yes
Since every input
will belong to either M2 No
L or its complement
L’.
Hence L is
recursive.
77
78