I thought this assignment is really interesting and worth posting about.<\/p>\n
CS 245 Assignment 5 Fall 2012<\/strong><\/p>\n \u2022 Form a set of clauses \u03a3 such that \u03a3 r TIMES(t1, t2, t3) whenever n1 \u00b7 n2 = n3; Question 2 (10pt) (a) the set \u039b\u2217 of all finite strings over \u039b is countable ; and<\/p>\n (b) the set of all countably-infinite sequences of symbols from \u039b is not countable. The solution I wrote is as follows (note question 1 required diagrams, so I did it in pen and it is not included here):<\/p>\n Let P be a ternary predicate symbol. Show that if \u2200x.\u2200y.\u2203z.P(x,y,z) is satisfiable, then also \u2200x.\u2200y.P(x,y,f(x,y)) is satisfiable.<\/p>\n Assume \u2200x.\u2200y.\u2203z.P(x,y,z) holds. \u25a1<\/p>\n (Question 3)<\/p>\n Let \u039b be a non-empty set of finite alphabets.<\/p>\n (a)<\/p>\n The set \u039b* of all finite strings over \u039b is countable.<\/p>\n We show there is an injection mapping f : \u039b*\u2192 \u2115 to the naturals. Let k denote the size of the alphabet, k = |\u039b|. To show countability, we introduce a method to inject the length of a string to the naturals. E.g. The set of all countably-infinite sequences of alphabets from \u039b is not countable.<\/p>\n By contradiction and Cantor\u2019s diagonalization, a string \u03c4n, where n denotes the arbitrary length of the string, can be constructed such that it is not in the set S of all countably-infinite sequence of alphabets. We show that \u03c4n is a string constructed from the alphabets \u039b, but it is not in the set S. Show that the satisfiability of first order logic (FOL) formula is undecidable.<\/p>\n Suppose it was decidable. Then that means given any FOL formula, there is an algorithm (another FOL formula) such that it can decide whether some formula is satisfiable. Okay, suppose such an algorithm exists. Let us denote it by SATISFIABLE(x), where x is any FOL formula. Hence \u2200xSATISFIABLE(x) would return a true if the input x was satisfiable, false if unsatisfiable. Now we write a new FOL formula EV IL(x) that calls SATISFIABLE, and returns its validity as follows: SATISIFABLE looks at EV IL and tries to determine if EV IL is satisfiable. If EV IL is satisfiable, then SATISFIABLE(EV IL) is unsatisfiable. But this is a contradiction, because it implies EV IL is unsatisfiable. For extra 10pt bonus show that satisfiability of first order formula is not recursively enumerable.<\/p>\n Suppose the set \u03a3 of satisfiable first order formula is recursively enumerable. By definition, \u03a3 is recursive if and only if \u03a3 and its complement \u03a3 are recursively enumerable. If we can tell if x\u03f5\u03a3, we have to be able to decide if x is not a member of \u03a3. M(x) returns 1 if M\u03a3(x) halts. M(x) returns 0 if M\u03a3(x) halts.<\/p>\n If we build M as a Turing machine, we have the answer because M decides the membership for a given set \u03a3. But it is not clear that M is indeed a Turing machine. For M to evaluate this, it must run M\u03a3(x) and M\u03a3(x) at the same time. This isn\u2019t hard if M has four tapes, two for computation for each computation. Since a Turing machine M of this property can be built, it can decide the membership for set \u03a3. I thought this assignment is really interesting and worth posting about. CS 245 Assignment 5 Fall 2012 Question 1 (30pt) Let ti be a term of the form s(\u00b7 \u00b7 \u00b7 s(0) \u00b7 \u00b7 \u00b7) that represents a natural number ni written in unary (e.g., s(s(s(0))) represents the number 3). \u2022 Form a set of … Continue reading CS245 regarding countability decidability<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-267","post","type-post","status-publish","format-standard","hentry","category-academica"],"_links":{"self":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/comments?post=267"}],"version-history":[{"count":10,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/267\/revisions"}],"predecessor-version":[{"id":594,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/267\/revisions\/594"}],"wp:attachment":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/media?parent=267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/categories?post=267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/tags?post=267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Question 1 (30pt)
\nLet ti be a term of the form s(\u00b7 \u00b7 \u00b7 s(0) \u00b7 \u00b7 \u00b7) that represents a natural number ni written in
\nunary
\n(e.g., s(s(s(0))) represents the number 3).<\/p>\n
\n\u2022 Show a resolution refutation of TIMES(s(s(0), s(0), s(s(0)))) w.r.t. \u03a3 from above;
\n\u2022 Is the set of terms {f (t1, t2, t3) | n1 \u00b7 n2 = n3} recursive?
\n
\nFor the first two parts you may use the clauses that define PLUS given in class.<\/p>\n
\nLet P be a ternary predicate symbol. Show that if \u2200x.\u2200y.\u2203z.P (x, y, z) is satisfiable then also
\n\u2200x.\u2200y.P (x, y, f (x, y)) is satisfiable.
\nQuestion 3 (20pt)
\nLet \u039b be a non-empty finite alphabet (set of symbols). Show that<\/p>\n
\nQuestion 4 (10pt; 10pt bonus)
\nShow that satisfiability of first order formul\u00e6 is undecidable.
\nFor extra 10pt bonus show that satisfiability of first order formul\u00e6 is not recursively enumerable.<\/code><\/p>\n(Question 2)<\/p>\n
\nThen for arbitrary \u03b1,\u03b2\u03f5D, there exists some \u03b3\u03f5D such that a substitution \u03b8 makes P true.
\nThe arbitrary substitution for I,\u03b8[u\u2215\u03b1,v\u2215\u03b2,w\u2215\u03b3]P(u,v,w) true, where u,v,w are subsituted and do not occur in P(x,y,z). Let \u03b8\u2032 be an arbitrary interpretation of domain D, such that \u03b8\u2032 agrees with \u03b8, except for f\u03b8\u2032(\u03b1,\u03b2) = \u03b3 (where f is some function).
\nSince \u2200x.\u2200y.\u2203z, by Skolemization method for removing existential quantifiers, a subsitution \u03b8\u2032 contains a function f based upon x and y, so that: I,\u03b8\u2032[u\u2215\u03b1,v\u2215\u03b2,w\u2215f\u03b8\u2032(\u03b1,\u03b2)]P(u,v,x).
\nSince f(u,v)\u03b8\u2032[u\u2215\u03b1,v\u2215\u03b2] = f\u03b8\u2032(\u03b1,\u03b2) = w\u03b8\u2032[u\u2215\u03b1,v\u2215\u03b2,w\u2215f\u03b8\u2032(\u03b1,\u03b2)] , meaning the arbituary w can be expressed in terms of a subsitution \u03b8\u2032. Thus I,\u03b8\u2032[u\u2215\u03b1,v\u2215\u03b2,w\u2215f\u03b8\u2032(\u03b1,\u03b2)]P(u,v,f(u,v)).
\nAnd it follows that \u2200x.\u2200y.P(x,y,f(x,y)).<\/p>\n
\nstrings of length 1 = k
\nstrings of length 2 = k \u00d7 k = k2
\nstrings of length * = k \u00d7 ... \u00d7 k = k*
\nWith this injection, any subset of strings can be counted and thus injected into the naturals. All of the \u039b* sub-strings are countable, and the union of all countable subsets is also countable. Since \u039b* is a set of finite strings, and the string length maps to a natural number, \u039b* is countable.
\n\u25a1
\n(b)<\/p>\n
\nSuppose S is countable. Then there exists a one-to-one correspondence that the elements s1,s2,...\u03f5S has a corresponding partner n1,n2,...\u03f5\u2115. We claim that such a correspondence does not exist by constructing a string \u03c4n to be different from every string in the set by at least one alphabet. We construct it in a diagonalization fashion:
\nIn \u03c4n, we change 1st alphabet at the first position in string s1. Then change 2nd alphabet at the second position in string s2.
\nFor example, let \u0393 be the English alphabet, and s1,s2,...\u03f5S be arbitrary. If s1 = \u201dabc\u201d, and s2 = \u201ddef\u201d, then when constructing \u03c4n: we pick a character that is not a from s1, and from s2 a character that is not e. In general, the ith alphabet in \u03c4n at the ith position in string si is to be replaced by some other alphabet. Continuing in this fashion generates a string \u03c4n that differs from every subset string s1,s2,...\u03f5S. Hence the string\u03c4n has no partner from S. Thus there is no one-to-one correspondence, and hence S is uncountable.
\n\u25a1
\n(Question 4)<\/p>\n
\nCall SATISFIABLE(x)
\nIf (true): return false.
\nOtherwise: return true.
\nWe feed the EV IL formula to SATISFIABLE. We claim that SATISFIABLE(EV IL) is a formula that cannot exist. Here is what a trace of the execution looks like:<\/p>\n
\nHowever, EV IL bases its result on SATISFIABLE\u2019s result.
\nWhatever the result is from SATISFIABLE, it makes EV IL unsatisfiable.
\nFrom this, we see that:<\/p>\n
\nIf EV IL is unsatisfiable, then SATISFIABLE(EV IL) is satisfiable. Again, this is a contradiction, because SATISFIABLE says EV IL is satisfiable.
\nWe can conclude that no matter what the result is of this execution, there are only contradictory results. This means the algorithm SATISFIABLE cannot form a valid conclusion - as the conclusions are all contradictory. Hence our assumption must be wrong, and hence the satisfiability of FOL formula is undecidable.
\n\u25a1
\n(Question 4) Bonus<\/p>\n
\nSince \u03a3 and\u03a3 are recursive sets, then by definition there exist Turing machines that accept them. Let M\u03a3 accept the set \u03a3 and M\u03a3 accept its compliment \u03a3. Now consider the following construction of such a machine:<\/p>\n
\nNote: one of M\u03a3(x) or M\u03a3(x) must halt, by construction.
\nHowever, this conclusion is a contradiction with part (a), which shows that the satisfiability of the first order logic formula is undecidable. This means we are incorrect in assuming \u03a3 is recursively enumerable. Hence the satisfiability of first order logic formula is not recursively enumerable.
\n\u25a1
\n<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"