Unit 5 | unit 5 undecidability

Back to Study material

FLAT

Unit - 5

Undecidability

5.1 Church-Turing thesis

In 1936, a technique named as lambda-calculus was created by Alonzo Church

Within which the Church numerals area unit well outlined, i.e. the encryption of

Natural numbers. Additionally, in 1936, mathematician machines (earlier known as

Theoretical model for machines) was created by mathematician, that’s used for

Manipulating the symbols of string with the assistance of tape.

Church - Turing Thesis:

Turing machine is outlined as associate degree abstract illustration of a computer

Like hardware in computers. Mathematician planned Logical Computing Machines

(LCMs), i.e., mathematician’s expressions for Turing Machines. This was done to

Outline algorithms properly. So, Church created a mechanical methodology named

As ‘M’ for manipulation of strings by mistreatment logic and arithmetic.

This methodology M should pass the subsequent statements:

• Number of directions in M should be finite.

• Output ought to be made when playing a finite variety of steps.

• It mustn’t be imagined, i.e., is created in the world.

• It mustn’t need any complicated understanding.

Using these statements Church planned a hypothesis known as Church’s

Mathematician thesis that may be expressed as: “The assumption that the intuitive

Notion of estimable functions is known with partial algorithmic functions.”

In 1930, this statement was initial developed by Alonzo Church and is typically

Brought up as Church’s thesis, or the Church-Turing thesis. However, this hypothesis

Cannot be proved .

The algorithmic functions are estimable when taking following assumptions:

1. Every and each operate should be estimable.

2. Let ‘F’ be the estimable operation and when playing some elementary operations to ‘F’, it’ll rework a replacement operation ‘G’ then this operates ‘G’ mechanically becomes the estimable operation.

3. If any operates that follow on top of 2 assumptions should be states as

Estimable function.

What Justifies the Church-Turing Thesis?

Stephen Kleenewho coined the term “Church-Turing thesis “catalogued four sorts of argument for CTT-O:

Initial, the argument from non-refutation points out the thesis has ne’er been refuted, despite sustained (and ongoing) makes an attempt to search out a disproof (such because the makes an attempt by László Kalmár and, additional

Recently, by Doukas Kapantais).

Second, the argument from confluence points to the

Very fact that the assorted characterizations of computability, whereas differing in

Their approaches and formal details, end up to comprehend the exact same category

Of estimable functions. Four such characterizations were bestowed (independently)

In 1936 and like a shot proved to be extensionally equivalent: mathematician

Computability, Church’s -definability, Kleene’s algorithmic functions, and Post’s

Finitary combinatory processes.

Third is associate degree argument typically brought up today as “Turing’s analysis.”

Mathematician known as it merely argument “I”; stating 5 terribly general and

Intuitive constraints or axioms the human pc is also assumed to satisfy: “The behavior

Of the pc at any moment is set by the symbols that he’s perceptive, associate

Degreed his “state of mind” at that moment”.

The second a part of mathematician’s argument I may be a demonstration that every

Operate computed by any human pc subject to those constraints is additionally

Estimable by a computing machine; it’s not tough to visualize that every of the

Computer’s steps is mimicked by the Turing machine, either during a single step or

By means that of a series of steps.

Fourth during this catalog of issues supporting CTT-O area unit arguments from first-

Order logic. They’re typified by a 1936 argument of Church’s and by Turing’s

Argument II, from Section nine of Turing’s 1936 paper. In 2013, Saul Kripke

Bestowed a reconstruction of Turing’s argument II, which works as follows:

Computation may be a special variety of mathematical deduction; each|and each}

Mathematical deduction and thus every computation can be formalized as a legitimate deduction within the language of first-order predicate logic with identity (a step Kripke brought up as “Hilbert’s thesis”); following Gödel’s completeness theorem, every computation is so formalized by a obvious formula of first-order logic; and each computation will thus be disbursed by the universal computing machine. This last step concerning the universal computing machine is secured by a theorem proved by Turing: each obvious formula of first-order logic is proved by the universal computing machine.

The third and fourth of those arguments offer justification for CTT-O however not for

CTT-A. As Robin Gandy found out, the third argument Turing’s I contains “crucial

Steps ... Wherever he [Turing] appeals to the very fact that the calculation is being

Disbursed by a person’s being.” as an example, mathematician assumed “a soul will

Solely write one image at a time, “associate degreed Gandy noted this assumption

Cannot be carried over to a parallel machine that “prints an discretionary variety of

Symbols at the same time.” In Conway’s Game of Life, for example, there’s no edge

On the number of cells that conjure the grid, nevertheless the symbols altogether the

Cells area unit updated at the same time. Likewise, the fourth argument (Turing’s II)

Involves the claim that computation may be a special variety of formal proof,

However, the notion of proof is in and of itself associated with what a person’s

Mathematician and not some oracle can prove.

It is thus perhaps not too surprising that the third and fourth arguments in this catalog seldom if ever appear in logic and computer science textbooks. The two arguments that are always given for the Church-Turing thesis (in, for example, Lewis and Papadimitriou are confluence and non-refutation. Yet both those arguments are

Merely inductive, whereas the third and fourth arguments are deductive in nature.

However, a number of attempts have sought to extend Turing’s axiomatic analysis to

Machine computation; for example, Gandy broadened Turing’s analysis in such a

Way that parallel computation is included, while Dershowitz and Gurevich gave a

More general analysis in terms of abstract state machines. We return to the topic of

Extending the analysis to machine computation later in this article but first address

The important question of whether CTT-O is mathematically provable.

Key takeaway:

- Turing machine is outlined as associate degree abstract illustration of a computer like hardware in computers.

- A common one is that a Turing machine can perform any good computation.

- The Church-Turing thesis is often misunderstood, especially in the philosophy of mind in recent writing.

5.2 Universal Turing machine

A Turing Machine is the mathematical tool equivalent to a digital computer. It was

Suggested by the mathematician Turing in the 30s, and has been since then the

Most widely used model of computation in computability and complexity theory.

The model consists of an input output relation that the machine computes. The input

Is given in binary form on the machine’s tape, and the output consists of the contents

Of the tape when the machine halts.

What determines how the contents of the tape change is a finite state machine (or

FSM, also called a finite automaton) inside the Turing Machine. The FSM is

Determined by the number of states it has, and the transitions between them.

At every step, the current state and the character read on the tape determine the

Next state the FSM will be in, the character that the machine will output on the tape

(possibly the one read, leaving the contents unchanged), and which direction the

Head moves in, left or right.

The problem with Turing Machines is that a different one must be constructed for

Every new computation to be performed, for every input output relation.

This is why we introduce the notion of a universal turing machine (UTM), which

Along with the input on the tape, takes in the description of a machine M. The UTM

Can go on then to simulate M on the rest of the contents of the input tape. A universal turing machine can thus simulate any other machine.

Fig 1: universal Turing machine

I learned about Turing Machines the first term of my sophomore year at MIT (Fall

96), in 6.004 (Computational Structures), the best class ever conceived. It was late

One night when I was starting my problem set on writing a turing machine to compute some operation. To test my result, I figured I could code up a Universal Turing Machine in Scheme to help me do my problem set. I could then feed it my

Description and a sample input, and it would simulate any machine for me. To me

Surprise within two hours, the program was working, and i could start the rest of me

Problem set

Program used to check solutions to a 6.004 problem set

;; Simulation of a Turing machine

;; global variables used by procedures.

;; Those are changed at every step, and must be reinitialized before running a

Different

;; example, by running: (setup state-graph tape initial-state initial-position)

(define *machine* ‘()); the machine currently running

(define *state* ‘s1); the state at which the current machine is at

(define *position* 0); the position at which the tape is reading

(define *tape* # ()); the tape that the current machine is currently running on

;; The following procedure takes in a state graph (see examples below), and turns it

;; to a machine, where each state is represented only once, in a list containing:

;; a structure of the form:

;; ((state (in out move next-state) (in out move next-state) (in out move next-state))

;; (state2 (in out move next-state))

;; (state3 (in out move next-state) (in out move next-state)))

;;

;; Each state name is followed by a list of combinations of inputs (read on the tape)

;; and the corresponding output (written on the tape), direction of motion (left or right),

;; and next state the machine will be in.

;;

;; Here’s the machine returned by (initialize flip) (as defined at the end of this file)

;; ((s4 (0 0 l h))

;; (s3 (1 1 r s4) (0 0 l s3))

;; (s2 (0 1 l s3) (1 0 r s2))

;; (s1 (0 1 r s2) (1 1 l s1)))

(define (initialize state-graph)

(define (extend machine states-to-go)

(if (null? states-to-go)

Machine

(let ((cur-state (first states-to-go))

(matched #f))

(extend (begin (for-each (lambda (state)

(if (equal? (state-name state) (car cur-state))

(begin (set! matched #t)

(set-cdr! state (cons (cdr cur-

State) (cdr state))))))

Machine)

(if matched

Machine

(cons (list (state-name cur-state)

(cdr cur-state))

Machine)))

(cdr states-to-go)))))

(extend ‘() state-graph))

;; Setup is a handy procedure to initialize and test a new graph.

;; It will take care of reading the graph, and initializing the global variables.

;; Once this is done, all one has to do is run the program (run) or move step

;; by step (step) for debugging

(define (setup state-graph tape state position)

(set! *machine* (initialize state-graph))

(set! *tape* tape)

(set! *state* state)

(set! *position* position))

;; The following are the procedures that implement the Turing machine.

;; It can write, read, move, etc...

(define (set-state! state)

(set! *state* state))

(define (set-position! position)

(set! *position* position))

(define (do-move move-to-make)

(cond ((equal? move-to-make ‘R) (move-right))

((equal? move-to-make ‘L) (move-left))

(else (error “i don’t know what move to make:”move-to-make))))

(define (move-right)

(set! *position* (+ *position* 1)))

(define (move-left)

(set! *position* (- *position* 1)))

(define (write output)

(vector-set! *tape* *position* output))

(define (read)

(vector-ref *tape* *position*))

Key takeaway:

- A Turing Machine is the mathematical tool equivalent to a digital computer.

- The model consists of an input output relation that the machine computes.

- A universal turing machine can thus simulate any other machine.

5.3 The universal and diagonalization languages

The resolving Language

1. Reducing One drawback to a different

Suppose we’ve Associate in Nursing algorithmic program A to rework instances of 1

Drawback P1 to instances of another drawback P2 in such the way that a string w is

In P1 if and on condition that the reworked string A(w) is in P2. What this means is

That we are able to solve instances of drawback P1 by changing them to instances of

Drawback P2 so mistreatment the answer to drawback P2 to answer the first

Question. If we are able to try this, then we are going to say that A may be a

Reduction of P1 to P2.

Note that a discount from P1 to P2 should flip each instance of P1 with a

Affirmative Associate in Nursingswer to an instance of P2 with a affirmative answer,

And each instance of P1 with a no Associate in Nursingswer to an instance of P2

With a no answer.

We are going to oftentimes use this method to point out that drawback P2 is as

Exhausting as drawback P1.

The direction of the reduction is very important.

For instance, if there’s a discount from P1 to P2 and if P1 isn’t algorithmic, then P2

Cannot be algorithmic. (Why?)

Similarly, if there’s a discount from P1 to P2 and if P1 isn’t recursively

Calculable, then P2 cannot be recursively calculable. (Why?)

2. Enumerating the Binary Strings

In several proofs involving Alan Mathison Turing machines, we' d like to enumerate the binary strings and encipher computing machines in order that WIll|we are able to} seek advice from the ith binary string as wi and also the ith Alan Mathison Turing machine as Mi.

The binary strings area unit straightforward to enumerate. If w may be a binary

String, we have a tendency to shall treat 1w because the binary number i thus we are

Able to decision w the ith string.

Mistreatment this coding, the empty string is that the 1st string, zero the second,

One the third, 00 the fourth, 01 the fifth, and so on. Henceforward WIll|we'll|we are going to} seek advice from the ith string as wi.

3. Codes for Alan Mathison Turing machines

We are going to currently outline a code for all Alan Mathison Turing machines with

The input alphabet in order that every computing machine may be painted by a

Binary string. This may enable United States to speak regarding the ith computing

Machine as Mi. We are going to adopt the subsequent conventions:

We have a tendency to assume the states area unit q1, q2, . . ., qr for a few r. We

Have a tendency to assume q1 can continually be the beginning state. We have a

Tendency to assume q2 are going to be the sole acceptive state. We'd like only 1

Acceptive state if we have a tendency to assume the computing machine halts

Whenever it enters Associate in Nursing acceptive state.

We have a tendency to assume the tape symbols area unit X1, X2, . . . , Xs for a few

s. We have a tendency to assume X1 is zero, X2 is 1, and X3 is that the blank.

We have a tendency to assign integers D1 and D2 to the tape head directions left

And right.

Currently we are able to encipher a transition rule δ (qi, Xj) = (qk, Xl, Dm) as a binary

String C of the shape

0i10j10k 10l10m

Suppose their area unit n transition rules. The code for the complete computing

Machine is going to be the concatenation of the codes for all of the transitions (in

Some order) separated by pairs of 1’s:

C111C211 … Cn-111Cn

Note that there may be several encodings for identical computing machine.

We are able to encipher a try (Mi, w) consisting of a computing machine and a string

By appending 111 to the coding of the computing machine so appending the string

4. The resolving Language Ld isn’t Recursively calculable

We have a tendency to outline Ld, the resolving language, as follows:

Let w1, w2, w3, . . . Be Associate in Nursing enumeration of all binary strings.

Let M1, M2, M3, . . . Be Associate in Nursing enumeration of all Alan Mathison

Turing machines.

Let Ld = American state | Wisconsin isn’t in L(Mi) }.

Theorem: Ld isn’t a recursively calculable language.

Proof:

Suppose Ld = L(Mi) for a few atomic number 69 Mi.

This offers rise to a contradiction. Take into account what Mi can do on Associate in

Nursing input string Wisconsin.

If Mi accepts Wisconsin, then by definition Wisconsin cannot be in Ld.

If Mi doesn’t accept Wisconsin, then by definition Wisconsin is in Ld.

Since Wisconsin will neither be in Ld nor not be in Ld, we have a tendency to

Should conclude there’s no computing machine which will outline Ld.

Identifying languages (or problems*) as decidable, undecidable or part decidable

May be a quite common question in GATE. With correct data and ample expertise,

This question becomes terribly straightforward to unravel.

Let’s begin with some definitions:-

Decidable language -A call drawback P is claimed to be decidable (i.e., have

Associate in Nursing algorithm)

If the language L of all affirmative instances to P is decidable.

Example- (I) (Acceptance drawback for DFA) Given a DFA will it settle for a given

Word?

(II) (Emptiness drawback for DFA) Given a DFA will it settle for any word?

(III) (Equivalence drawback for DFA) Given 2 DFAs, do they settle for the

Same language?

Undecidable language -– a call drawback P is claimed to be undecidable if the

Language L of all yes instances to P isn’t decidable or a language is undecidable if it’s not decidable.

Associate in Nursing undecidable language perhaps a part decidable language or

One thing else however not decidable. If a language isn’t even part decidable , then

There exists no computing machine for that language.

Partially decidable or Semi-Decidable Language -– a call drawback P is claimed to

Be semi-decidable (i.e., have a semi-algorithm) if the language L of all affirmative

Instances to P is RE. A language ‘L’ is part decidable if ‘L’ may be a RE however not

REC language.

Recursive language(REC) – A language ‘L’ is alleged to be algorithmic if there exists

a computing device which is able to settle for all the strings in ‘L’ and reject all the

Strings not in ‘L’. The computing device can halt on every occasion and provides

Associate answer(accepted or rejected) for every and each string input. A language

‘L’ is decidable if it’s a algorithmic language. All decidable languages area unit

Algorithmic languages and vice-versa.

Recursively countable language(RE) – A language ‘L’ is alleged to be a recursively

Countable language if there exists a computing device which is able to settle for (and

So halt) for all the input strings that area unit in ‘L’ however could or might not halt for

All input strings that aren’;t in ‘L’. By definition , all REC languages {are also|also area

Unit|are} RE languages however not all RE languages are REC languages.

Now lets solve some examples –

a method to unravel decidability issues is by {trying|making associate

Attempt|attempting} to cut back an already illustrious undecidable downside to the

Given downside. By reducing a retardant P1 to P2, we tend to mean that we tend to

Try to unravel P1 by mistreatment the formula wont to solve P2.

If we are able to cut back associate already illustrious undecidable downside P1 to a

Given downside P2 , then we are able to sure enough say that P2 is additionally

Undecidable. If P2 was decidable, then P1 would even be decidable however that

Becomes a contradiction as a result of P1 is understood to be undecidable.

For example:

1. Given a computing device ‘M’, we want to seek out out whether or not a state ‘Q’

Is ever reached once a string ‘w’ is entered in ‘M’. This downside is additionally

Referred to as the ‘State Entry problem’.

Now lets try and cut back the Halting downside to the State Entry downside. A

Computing device solely halts once a transition operate ? (qi , a) isn't outlined.

Modification each indefinable operate ?(qi,a) to ?(qi,a) = (Q, a, L or R). Note that the

State letter will solely be reached once the computing device halts.

Suppose we’ve have associate formula for finding the State Entry downside which is

Able to halt on every occasion and tell United States of America whether or not state

Letter will be reached or not. By telling United States of America that we are able to

Or cannot reach state letter on every occasion, it’s telling United States of America that the computing device can or won’t halt, every time. However, we all know that’s impractical as a result of the halting downside is undecidable. Meaning that us

Assumption that there exists associate formula that solves the State Entry downside

And halts and offers United States of America a solution on every occasion, is false.

Hence, the state entry downside is undecidable.

Key takeaway:

- This techniques was introduced in 1873 by Georg Cantor

- As a way of showing that the (infinite) set of real numbers is larger than the (infinite) set of integers

5.4 Reduction between languages and Rice’s theorem

Rice theorem states that any non-trivial linguistics property of a language that is

Recognized by a information processing system is undecidable. A property, P, is that

The language of all Alan Mathison Turing machines that satisfy that property.

Formal Definition

If P may be a non-trivial property, and therefore the language holding the property,

Lp , is recognized by information processing system M, then record = L(M) ∈ P is

Undecidable.

Description and Properties

• Property of languages, P, is solely a collection of languages. If any language

Belongs to P (L ∈ P), it's aforesaid that L satisfies the property P.

• A property is named to be trivial if either it's not happy by any recursively

Numerable languages, or if it’s happy by all recursively numerable languages.

• A non-trivial property is happy by some recursively numerable languages and

Aren’t happy by others. Formally speaking, in an exceedingly non-trivial property,

Wherever L ∈ P, each the subsequent properties hold:

o Property one one There exists Alan Mathison Turing Machines, M1 and M2

That acknowledge constant language, i.e. either (, ∈ L) or (, ∉ L)

o Property two two There exists Alan Mathison Turing Machines M1 and M2,

Wherever M1 acknowledges the language whereas M2 doesn’t, i.e. ∈ L and ∉ L

Proof

Suppose, a property P is non-trivial and φ ∈ P.

Since, P is non-trivial, a minimum of one language satisfies P, i.e., L(M0) ∈ P , ∋

Information processing system M0.

Let, w be associate degree input in an exceedingly specific instant and N may be a

Information processing system that follows −

On input x

● Run M on w

● If M doesn’t settle for (or does not halt), then don't settle for x (or don’t halt)

● If M accepts w then run M0 on x. If M0 accepts x, then settle for x.

A perform that maps associate degree instance ATM = M accepts input w to a N such

● If M accepts w and N accepts constant language as M0, Then L(M) = L(M0) ∈ p

● If M doesn’t settle for w and N accepts φ, Then L(N) = φ ∉ p

Since ATM is undecidable and it is reduced to record, record is additionally undecidable.

Decidable issues

A problem is decidable if we will construct a information processing system which

Can halt in finite quantity of your time for each input and provides answer as ‘yes’ or

‘no’. A decidable downside has associate degree formula to work out the solution for

a given input.

Examples

• Equivalence of 2 regular languages: Given 2 regular languages, there’s

Associate degree formula and information processing system to make a decision

Whether or not 2 regular languages ar equal or not.

• Finiteness of normal language: Given an everyday language, there’s

Associate degree formula and information processing system to make a decision

Whether or not regular language is finite or not.

• Emptiness of context free language: Given a context free language, there’s

Associate degree formula whether or not CFL is empty or not.

Undecidable issues

A problem is undecidable if there’s no information processing system which can

Continuously halt in finite quantity of your time to provide answer as ‘yes’ or ‘no’.

Associate degree undecidable downside has no formula to work out the solution for a

Given input.

Examples

• Ambiguity of context-free languages: Given a context-free language, there’s

No information processing system which can continuously halt in finite quantity of

Your time and provides answer whether or not language is ambiguous or not.

• Equivalence of 2 context-free languages: Given 2 context-free languages,

There’s no information processing system which can continuously halt in finite

Quantity of your time and provides answer whether or not 2 context free languages ar

Equal or not.

• Everything or completeness of CFG: Given a CFG and input alphabet,

Whether or not CFG can generate all doable strings of input alphabet (∑*)is

Undecidable.

• Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC,

Determinative whether or not this language is regular is undecidable.

Note: 2 in style undecidable issues ar halting downside of metal and angel dust (Post

Correspondence Problem). Semi-decidable issues

A semi-decidable downside is set of undecidable issues that information processing

System can continuously halt in finite quantity of your time for answer as ‘yes’ and

Will or might not halt for answer as ‘no’.

Rice’s Theorem

Every non-trivial (answer isn’t known) downside on algorithmic numerable languages is undecidable.e.g.; If a language is algorithmic numerable, its complement are going to be algorithmic numerable or not is undecidable.

Reducibility and Undecidability

Language A is reducible to language B (represented as A≤B) if there exists a

Perform f which can convert strings in an exceedingly to strings in B as:

w ɛ A <=> f(w) ɛ B

Theorem 1: If A≤B and B is decidable then A is additionally decidable.

Theorem 2: If A≤B and A is undecidable then B is additionally undecidable.

Key takeaway:

- The Rice theorem states that every non-trivial semantic characteristic of a language that a Turing machine recognises is undecidable.

- If we can create a Turing machine that will stop for each input in a finite amount of time and respond as 'yes' or 'no', a problem is determinable.

- An algorithm for determining the answer to a given input has a decidable.

5.5 Undecidable problems about languages

For an undecidable language, there is no Turing Machine which accepts the

Language and makes a decision for every input string w (TM can make decision for

Some input string though).

A decision problem P is called “undecidable” if the language L of all yes instances to P is not decidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages.

Fig 2: undecidable language

Example

● The halting problem of Turing machine

● The mortality problem

● The mortal matrix problem

● The Post correspondence problem, etc.

Halting problem of turing machine

Input : A machine with Turing and an input string w.

Problem : Does the Turing machine complete the w-string computation in a finite number of steps? Either yes or no must be the answer.

Proof : We will first assume that there is such a Turing machine to solve this problem, and then we will demonstrate that it contradicts itself. This Turing machine would be called a Halting machine that produces in a finite amount of time a 'yes' or 'no'. The performance comes as 'yes' if the stopping machine finishes in a finite amount of time, otherwise as 'no'.

The Halting Computer block diagram is as follows.