2
$\begingroup$

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.

$\endgroup$
1
7
$\begingroup$

Diophantine equations with a solution

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.