# Differences

This shows you the differences between two versions of the page.

 sav08:recursive_set [2008/03/18 18:03]vkuncak created sav08:recursive_set [2008/03/18 18:04] (current)vkuncak 2008/03/18 18:04 vkuncak 2008/03/18 18:03 vkuncak created 2008/03/18 18:04 vkuncak 2008/03/18 18:03 vkuncak created Line 1: Line 1: ====== Recursive Set ====== ====== Recursive Set ====== - We say that a set $S$ is //​recursive//​ if there exists an algorithm that, given an element $x$ determines whether $x \in S$ holds. + We say that a set $S$ is //​recursive// ​(decidable) ​if there exists an algorithm that, given an element $x$ determines whether $x \in S$. Example: the set of even numbers is recursive. ​ The algorithm takes $x$ represented in binary and checks whether its least signifficant digit is 0. Example: the set of even numbers is recursive. ​ The algorithm takes $x$ represented in binary and checks whether its least signifficant digit is 0. Line 7: Line 7: Example: the set of all pairs $(T,x)$ such that $T$ is a representation of Turing machine and $x$ is an input such that $T$ terminates on input $x$, is not recursive. Example: the set of all pairs $(T,x)$ such that $T$ is a representation of Turing machine and $x$ is an input such that $T$ terminates on input $x$, is not recursive. + Example: the set of encodings of all valid first-order logic formulas is not recursive. + + Example: the set of all valid formulas of Presburger arithmetic is recursive.