0
$\begingroup$

Let's say our Σ is 0 and 1. I want to disprove the following:

There can be Turing Machines that accept only 1's, i.e. 1, 11, 111, etc. Therefore, all languages that have strings of 1's are recognizable.

My first step to proving this is by providing a language such as $One$, that accepts only if $w$ contains only $1$'s. There is a theorem that stated that $One$ is decidable iff $One$ and $\overline{One}$ are recognizable.

So, if I were to prove either one of them as unrecognizable, then I should be good. $\overline{One}$ I'll define as the set that doesn't contain 1 in it (i.e. episolon, 0, 00, etc). Creating a turing machine that simply goes right and accepts if we reach end without hitting a one, rejects if we do hit a one seems to work for this case. Could a language be created that isn't recognizable?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Please clarify the following in the question. A) "There can be Turing Machines that contain only 1's, i.e. 1, 11, 111, etc. " If you formulate that proposition by yourself, please claim your originality. If you read it somewhere, please give a reference. B) Nobody will say "Turing Machines that contain only 1's, i.e. 1, 11, 111, etc." Do you mean "Turing Machines that accept only 1's, i.e. 1, 11, 111, etc"? C) I have not seen the definition of $One$. Do you mean the language of all words that contain at least one 1? $\endgroup$
    – John L.
    Feb 20, 2019 at 23:05
  • $\begingroup$ A) Created to better understand a concept B) Clarifications, Turing Machines that only accept, edited question C) $One$ is the one that contains only ones $\endgroup$
    – Andrew Raleigh
    Feb 21, 2019 at 14:30
  • 2
    $\begingroup$ So $Ones = \{1^n\mid n>0\}$? If so, its complement will also contain strings like 01, as well. Finally, with regard to your penultimate sentence, there are plenty of infinite recognizable languages. $\endgroup$
    – Rick Decker
    Feb 21, 2019 at 15:07
  • $\begingroup$ I thought it's complement would be any strings that don't contain 1? Are in this case would it be strings that don't only contain 1? Are there any non recognizable/decidable languages for this? $\endgroup$
    – Andrew Raleigh
    Feb 21, 2019 at 15:22
  • 1
    $\begingroup$ @AndrewRaleigh No, the complement of a language is the set of all strings not in it. So the complement of $One$ is the set of all strings that aren't just $1$s -- that is all strings that only contain $0$s, plus all strings with a mixture of $0$s and $1$s. $\endgroup$
    – David Richerby
    Feb 21, 2019 at 18:36

2 Answers 2

Reset to default
1
$\begingroup$

(I would post this as a comment but I need 50 reputation to comment... so...)

I think this might be solved using cardinality,
You have $2^{\aleph_0}$ languages of such property (power set of $\{ 1^n | n>0 \}$).
While $|RE| = \aleph_0$

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't really follow since I'm not very knowledgeable with cardinality, can you explain how this shows it to be non recognizable? $\endgroup$
    – Andrew Raleigh
    Feb 21, 2019 at 15:49
  • 1
    $\begingroup$ Imagine that you have 10 languages but only 5 machines. It's not possible for you to have a machine for every language $\endgroup$
    – Shahaf Finder
    Feb 21, 2019 at 15:51
  • $\begingroup$ The pigeon hole theory wasn't it? The notation you're using isn't familiar though, can you explain it in English? $\endgroup$
    – Andrew Raleigh
    Feb 21, 2019 at 15:57
  • 1
    $\begingroup$ Yes, the pigeon hole theory. It might not be easy to follow if you're not familiar with set theory, I'll try to explain but I might miss something. The notation $\aleph_0$ is used for a cardinality of the natural numbers (a countable set). You can find the proof that the cardinality of the power set (the set of all subsets) of a countable set is $2^{|\aleph_0|}$, and $2^{\aleph_0}>\aleph_0$. so we have a set that's larger (and not possibly equal) to another, so you can use the pigeon hole theory. $\endgroup$
    – Shahaf Finder
    Feb 21, 2019 at 16:02
  • 1
    $\begingroup$ My answer states that there is a language that only have words made of 1's, that doesn't have a turing machine that accepts it. I didn't try to show which language (which might not be possible to show) $\endgroup$
    – Shahaf Finder
    Feb 21, 2019 at 16:31
2
$\begingroup$

It isn't recognizable because it is infinite, therefore it'll loop infinitely. Does this work?

No, because that claim is false. And your writing isn't at all clear, here. Recognizability is a property of languages, so your first two "it"s must refer to languages; but "loops infinitely" is a property of Turing machines, so your third "it" must be one of those.

Ultimately, though, your whole approach is doomed because the languages you call $One$ and $\overline{One}$ are both decidable. You can easily see that $One$ is decidabe just by designing a Turing machine that decides it.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is there another approach I should be taking here? You're right, going to change my question to clarify. $\endgroup$
    – Andrew Raleigh
    Feb 21, 2019 at 18:12
  • 2
    $\begingroup$ @AndrewRaleigh Shahaf's cardinality approach quickly shows that there are (many!) unrecognizable languages even over alphabet $\Sigma=\{1\}$. Is there any reason you're forbidding proofs by reduction? It's easy to code languages over alphabet $\{0,1\}$ as languages over $\{1\}$ -- roughly speaking, a string of $0$s and $1$s is a number $n$ in binary, so encode it as $n$ $1$s. $\endgroup$
    – David Richerby
    Feb 21, 2019 at 18:34
  • $\begingroup$ No reductions because I'm unfamiliar with it, meaning the provide an unrecognizable language is through carnality or reduction then? If so, what's a way to do this through reduction? $\endgroup$
    – Andrew Raleigh
    Feb 22, 2019 at 16:07
  • $\begingroup$ @AndrewRaleigh Reductions are the single most important technique in proving hardness of problems (both in computability and complexity). You should absolutely learn about them before trying to go any farther. Basically, I already told you how to do it with reductions in my previous comment, which I think you'll recognize once you know about them. $\endgroup$
    – David Richerby
    Feb 22, 2019 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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