# 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 |
||
---|---|---|---|

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. | ||