5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can I ask what you mean by this being Kleene Star? $\endgroup$ – Andrew Raleigh Feb 13 at 20:43
  • 1
    $\begingroup$ @AndrewRaleigh "Kleene star of $L$" or "$L^*$" means "concatenate $x$ things from language $L$, $x \in \mathbb{N}$". $\endgroup$ – Draconis Feb 13 at 21:13
  • 1
    $\begingroup$ What do you mean by the TM being recognizable? A TM and the language it accepts are different things. $\endgroup$ – Stop Harming Monica Feb 14 at 15:25
  • $\begingroup$ Rice's theorem would seem to imply that there is no TM recognizing which TMs recognize the language $\{ 1^x \mid x > 0 \}$. Which is how I initially interpreted the question based on the wording... $\endgroup$ – Daniel Schepler Feb 14 at 19:13
  • $\begingroup$ @DanielSchepler Can you expand on that? I was looking into solving it using Rice's theorem as my interpretation is that it is unrecognizable. $\endgroup$ – Andrew Raleigh Feb 14 at 21:02
21
$\begingroup$

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

$\endgroup$
  • 19
    $\begingroup$ @AndrewRaleigh Sure, the language $\{1^x \mid x \in \mathbb{N} \}$ is infinite. However, all its elements are finitely long. $\endgroup$ – Draconis Feb 13 at 20:48
  • 4
    $\begingroup$ @AndrewRaleigh That's exactly the same language, except that you're allowing the empty string in it now. $\endgroup$ – Draconis Feb 13 at 21:12
  • 6
    $\begingroup$ I think a slightly different way of phrasing it is: there's a difference between being able to accept all strings (which is an infinite set) vs being able to accept any string (which is part of that infinite set, but is itself not infinite). $\endgroup$ – yshavit Feb 14 at 5:53
  • 1
    $\begingroup$ @yshavit does that mean than an infinite set (accept all strings) is not allowed/possible but accepting any string from a set (which can be infinite) is allwowed/possible because any string is not infinite even it's part of an infinite set? I'm sorry but that's confusing for me $\endgroup$ – undefined Feb 14 at 10:42
  • 3
    $\begingroup$ @undefined Exactly. Think about it this way: if I gave you an integer, could you tell me if it's even? Sure, it'd be easy! And yet the set of integers is infinite. Same idea. $\endgroup$ – yshavit Feb 14 at 15:33
6
$\begingroup$

Languages are sets of finite strings. Every input to a Turing machine is a finite string. $1^\infty$ is a thing, but not in this model of computation (and usually we're more specific about what infinity we're talking about).

$\endgroup$
  • 1
    $\begingroup$ " Languages are sets of finite strings." This is of course true by definition. Infinite strings certainly do exist, e.g. the digits of 1/3 and those of pi, we just exclude such strings from our definition here. $\endgroup$ – MSalters Feb 14 at 15:53
  • $\begingroup$ @MSalters And there's a whole theory of automata dealing with those infinite strings. But that's a different theory to what we're dealing with here. $\endgroup$ – David Richerby Feb 14 at 17:07
1
$\begingroup$

A few answers has addressed the confusion about the length of a word being infinite.

Here I would like to address the following question.

A better way to phrase my question is: Is there a language of any number of 1s over $\Sigma=\{0,1\}$ that you can make unrecognizable?

Note that if a language of any number of 1s is unrecognizable, then it is unrecognizable over any alphabet that contains 1.

That question has been answered positively here. I would like to add another famous "constructive" example, busy beaver sequence, a.k.a. Rado's sigma function. Let $\sigma:\Bbb N\to\Bbb N$ be that function. We know that $$\sigma(0)=0,\ \sigma(1)=1,\ \sigma(2)=4,\ \sigma(3)=6,\ \sigma(4)=13, \\\sigma(5)\ge4098,\ \sigma(6)\ge 1.29*10^{865},\cdots. $$

We have not determine $\sigma(5)$ yet!

The language for $\sigma$ is $$\{1^{\sigma(n)}: n\in \Bbb N\}=\{\epsilon, 1, 1111, 111111, 1111111111111, \cdots\},$$ which is undecidable.

$\endgroup$
  • $\begingroup$ Note that if a language of any number of 1s is unrecognizable, then it is unrecognizable over any alphabet that contains 1. I don't get the answer provided in the link, it seemed to contradict what you're saying. Is the busy beaver sequence a counter proof? $\endgroup$ – Andrew Raleigh Feb 14 at 21:14
  • $\begingroup$ Please come to chat room for unrecognizable language over unary alphabet $\endgroup$ – Apass.Jack Feb 14 at 21:21
0
$\begingroup$

$1^\infty$ is not an actual word in the language, since $\infty$ is not a natural number - even though the language contains infinitely many words, each word has a finite, arbitrarily large length $n$.

A language is decidable if there is a Turing Machine can decide it in a finite number of steps for each input. That's obviously true here - there is no word that will take infinitely long to process.

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 1s over $Σ=\{0,1\}$ that you can make unrecognizable?

You mean an undecidable unary (consisting only of one symbol) language? Sure there is!

Take any language $L \in \{0,1\}^*$ that you already know to be undecidable. (For example, a language that encodes all halting Turing Machines.) Modify it a bit by adding "1" to the start of each word, to keep leading zeros.

Then let your language $L'$ consist of the word $1^n$ for every $n$ whose binary representation is in $L$. ~~As each word in $L$ can be easily turned into a word in $L'$~~*, a machine that decides $L'$ could be used to decide $L$. As $L$ is undecidable, so is $L'$.

Edit: *To be more precise: "As each binary word $w$ beginning with 1 can be converted into a word consisting of 1s $w'$ such that $w\in L$ iff $w' \in L'$..."

$\endgroup$
  • $\begingroup$ Nitpicking here. Suppose $L\subset \{0\}^*$ is undecidable.Then $L'=\{\epsilon\}$ (or what?) is decidable. $\endgroup$ – Apass.Jack Feb 14 at 18:47
  • $\begingroup$ I think the "prefix all words with 1 to fix leading zeros" part fixes this issue, but I haven't yet thought about it in detail. $\endgroup$ – Christoph Burschka Feb 14 at 20:14

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.