<p>Let $T$ be any recursively axiomatized but undecidable theory (such as arithmetic, set theory, etc.) Then the logical consequences of $T$ are recursively enumerable but not recursive.</p>

CC BY-SA 3.0
2012-01-06T18:03:51.053Z
2012-01-06T18:03:51.053Z
David Harris
<p>I am trying to find out if there exists a language, which is recursively enumerable but not recursive, but which wouldn't also use Gödel's number or any other kind of Turing machine description in its definition. The language should be possible to somehow "easily" describe. ("Easily" being purely subjective, I know.)</p>

<p>But each one I try to construct is either recursive or not recursively enumerable.</p>

CC BY-SA 3.0
2012-01-06T10:40:00.267Z
Most of the [examples of undecidable languages](http://en.wikipedia.org/wiki/List_of_undecidable_problems) in the literature are recursively enumerable.
Tsuyoshi Ito
<fl.formal-languages><examples>
Recursively enumerable, non-recursive language without using Gödel's number
Karel Bílek
# Recursively enumerable, non-recursive language without using Gödel's number

(Asked by: username_0 on 2012-01-06)

I am trying to find out if there exists a language, which is recursively enumerable but not recursive, but which wouldn't also use Gödel's number or any other kind of Turing machine description in its definition. The language should be possible to somehow "easily" describe. ("Easily" being purely subjective, I know.)

But each one I try to construct is either recursive or not recursively enumerable.

**Tags:** fl.formal-languages, examples
> **Comments:**
> **username_1**: Most of the [examples of undecidable languages](http://en.wikipedia.org/wiki/List_of_undecidable_problems) in the literature are recursively enumerable.  

---

## 1 answers

### Answer by username_2 on 2012-01-06. Score: 1

Let $T$ be any recursively axiomatized but undecidable theory (such as arithmetic, set theory, etc.) Then the logical consequences of $T$ are recursively enumerable but not recursive.


---

