HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Is the infinite language unrecognizable in a Turing machine?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitethelanguageunrecognizableturingmachine

Problem

This question is building up on an older one, here.

But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?

That means 1, 11, 11111, 1111111, and so on are all accepted.

I believe the TM is unrecognizable. This is because for it to be recognizable, we would have to halt. Yet, with no upper limit, we can have $1^\infty$ - meaning we will never halt. Does this work?

The above was an example of a language, didn't think it would be recognizable. A better way to phrase my question is: Is there a language of any number of $1$s over $\Sigma=\{0, 1\}$ that you can make unrecognizable?

Solution

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable.

A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we can indeed build a Turing machine that does this!

Algorithm:
    Check the number under the head.
    If it's 0, fail.
    If it's the end of the string, accept.
    If it's 1, move to the right and repeat.


The key is, while there's no upper limit, $x$ has to be a natural number—and $\infty$ is not a natural number. In other words, while $x$ can be arbitrarily large, it has to have some finite value. It can't actually be $\infty$.

Code Snippets

Algorithm:
    Check the number under the head.
    If it's 0, fail.
    If it's the end of the string, accept.
    If it's 1, move to the right and repeat.

Context

StackExchange Computer Science Q#104320, answer score: 21

Revisions (0)

No revisions yet.