There is a Turing machine that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.

Non-examples: cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages

Subset of recursively enumerable language as explained at: difference between recursive language and recursively enumerable language.

Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.

Is a decision problem of determining if something belongs to a non-recursive language.

Or in other words: there is no Turing machine that always halts for every input with the yes/no output.

Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.

Some undecidable problems are of recursively enumerable language, e.g. the halting problem.

Lists of undecidable problems.

Coolest ones besides the obvious boring halting problem:

One of the most simple to state undecidable problems.

The reason that it is undecidable is that you can repeat each matrix any number of times, so there isn't a finite number of possibilities to check.

A:

There are only boring examples of taking an uncomputable language and converting it into a number?

After removing it:

Of course, we already knew that minimal plaster work would be needed from the start, since we have to hammer two small nails into the wall. But that level of damage might have been easily dealt with by a non-professional tenant himself. But the level I had was a bit more than I felt I should handle myself.

Same as recursive language but in the context of the integers.

Qt front-end for FluidSynth.

The list: complexityzoo.uwaterloo.ca/Complexity_Zoo

Computational problem where the solution is either yes or no.

When there are more than two possible answers, it is called a function problem.

Decision problems come up often in computer science because many important problems are often stated in terms of "decide if a given string belongs to given formal language".

The canonical undecidable problem.

A Turing machine decider is a program that decides if one or more Turing machines halts of not.

Of course, because what we know about the halting problem, there cannot exist a single decider that decides all Turing machines.

E.g. The Busy Beaver Challenge has a set of deciders clearly published, which decide a large part of BB(5). Their proposed deciders are listed at: discuss.bbchallenge.org/c/deciders/5 and actually applied ones at: bbchallenge.org.

But there are deciders that can decide large classes of turing machines.

Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff hyperparameters, e.g. the cutoff space/time of a Turing machine cycler decider.

The simplest and most obvious example is the Turing machine cycler decider

Bibliography: discuss.bbchallenge.org/t/decider-cyclers/33

Example: bbchallenge.org/279081.

These are very simple, they just check for exact state repetitions, which obviously imply that they will run forever.

Unfortunately, cyclers may need to run through an initial setup phase before reaching the initial cycle point, which is not very elegant.

Also, we have no way of knowing the initial setup length of the actual cycle length, so we just need an arbitrary cutoff value.

And unfortunately, this can lead to misses, e.g. Skelet machine #1, a 5 state machine, has a (translated) cycle that starts at around 50-200M steps, and takes 8 trillion steps to repeat.

Bibliography: discuss.bbchallenge.org/t/decider-translated-cyclers/34

Like a cycler, but the cycle starts at an offset.

To see infinity, we check that if the machine only goes left N squares until reaching the repetition, then repetition must only be N squares long.