In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.

Watch related videos of your favorite subject.

Connect with students from different parts of the world.

Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE

See Our team

Wondering how we keep quality?

Got unsolved questions? Ask Questions

GATE
GMAT
CBSE
NCERT
Career
Interview
Railway
UPSC
NID
NIFT-UG
NIFT-PG
PHP
AJAX
JavaScript
Node Js
Shell Script
Research

## What is undecidability of predicate logic?

## in terms of logic of computers

Asked On2017-06-07 06:26:09 by:milan-ransingh

Taged users:

Nikhil-bharadwaj

Likes:

Be first to like this question

Dislikes:

Be first to dislike this question

Talk about this Like Dislike

Download question setAnswersTheorem: It is undecidable whether a first order logic formula is provable (or true under all possible interpretations).

Proof: Suppose there is an algorithm B that, given a first order logic and a formula in that logic, decides whether that formula is valid (holds under all possible interpretations). I will use that to give a decision algorithm for the language {(M,w) | M is the description of a Turing machine that accepts the string w}. As the latter problem is undecidable this will show that B cannot exists.

Given M and w, create a first order logic by declaring a constant , a unary function symbol

afor every letterain the alphabet, and a binary predicate f_{q}for every state q of M.Consider the following interpretation of this logic: Variables x range over strings over the given alphabet, denotes the empty string,

a(w) denotes the stringaw, and f_{q}(x,y) indicates that M, when given input w, can reach a configuration with state q, in which xy is on the tape, with x in reverse order, and the head of M points at the first position of y. Under this interpretation f_{q0}(,w) is certainly a true formula, as the initial configuration is surely reachable. Here q0 is the initial state, and w is a representation of w made from the constant and function symbols of the logic. Furthermore the formula x y: f_{q-acc}(x,y) with q-acc the acceptance state, holds iff M accepts w.Whenever M has a transition from state q to state r, reading a, writing b, and moving right, the formula

x y: f

holds. Here x and y are variables. Likewise, if M has a transition from state q to state r, reading a, writing b, and moving left, the formulas_{q}(x,ay) => f_{r}(bx,y)x y: f

hold for every choice of a letter c. In addition we have_{q}(cx,ay) => f_{r}(x,cby)x y: f

covering the case that M cannot move left, because its head is already in the left-most position. Finally, there are variants of the formulas above for the case that a is the blank symbol and that square of the tape is visited for the first time:_{q}(,ay) => f_{r}(,by),x y: f

Let T be the conjunction of all implication formulas mentioned above. As M has finitely many transitions and the alphabet is finite, this conjunction is finite as well, and thus a formula of first order logic. Now consider the formula_{q}(x,) => f_{r}(bx,)x y: f

_{q}(cx,) => f_{r}(x,cb)x y: f

_{q}(,) => f_{r}(,b).f

In case M accepts w, there is a valid computation leading to an accept state. Each step therein corresponds with a substitution instance of one of the conjuncts in T, and using the laws of first order logic it is easy to check that the formula above is provable and thus true under all interpretations. If, on the other hand, the formula above is true under all interpretations, it is surely true in the given interpretation, which implies that M has an accepting computation starting on w._{q0}(,w) & T => x y: f_{q-acc}(x,y).Thus, in order to decide whether or not M accepts w, it suffices to check whether or not the formula above is

Likes:

Be first to like this answer

Dislikes:

Be first to dislike this answer

Talk about this Like Dislike

Lets together make the web is a better placeWe made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams"with these.Answer a question:You can answer the questions not yet answered in eduladder.How to answer a questionCareer:Work or do your internship with us.Work with usCreate a video:You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder