Is the infinite language unrecognizable in a Turing machine?












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?






formal-languages turing-machines automata undecidability







share|cite|improve this question











$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$
    – OrangeDog
    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
















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?






formal-languages turing-machines automata undecidability







share|cite|improve this question











$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$
    – OrangeDog
    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














5












5








5


3



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






formal-languages turing-machines automata undecidability







share|cite|improve this question











$endgroup$




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?






formal-languages turing-machines automata undecidability




formal-languages turing-machines automata undecidability






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 14 at 14:30







Andrew Raleigh

















asked Feb 13 at 20:07









Andrew RaleighAndrew Raleigh

566




566












  • $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$
    – OrangeDog
    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


















  • $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$
    – OrangeDog
    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
















$begingroup$
Can I ask what you mean by this being Kleene Star?
$endgroup$
– Andrew Raleigh
Feb 13 at 20:43




$begingroup$
Can I ask what you mean by this being Kleene Star?
$endgroup$
– Andrew Raleigh
Feb 13 at 20:43




1




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




$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




1




$begingroup$
What do you mean by the TM being recognizable? A TM and the language it accepts are different things.
$endgroup$
– OrangeDog
Feb 14 at 15:25




$begingroup$
What do you mean by the TM being recognizable? A TM and the language it accepts are different things.
$endgroup$
– OrangeDog
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$
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




$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










4 Answers
4






active

oldest

votes


















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






share|cite|improve this answer









$endgroup$









  • 18




    $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



















5












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






share|cite|improve this answer









$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 NtoBbb 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)}: nin Bbb N}={epsilon, 1, 1111, 111111, 1111111111111, cdots},$$
which is undecidable.








share|cite|improve this answer









$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 $win L$ iff $w' in L'$..."






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Nitpicking here. Suppose $Lsubset {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





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104320%2fis-the-infinite-language-unrecognizable-in-a-turing-machine%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























4 Answers
4






active

oldest

votes








4 Answers
4






active

oldest

votes









active

oldest

votes






active

oldest

votes









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






share|cite|improve this answer









$endgroup$









  • 18




    $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
















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






share|cite|improve this answer









$endgroup$









  • 18




    $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














21












21








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






share|cite|improve this answer









$endgroup$



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







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 13 at 20:28









DraconisDraconis

5,312821




5,312821








  • 18




    $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














  • 18




    $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








18




18




$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




$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




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




$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




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




$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




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




$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




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




$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











5












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






share|cite|improve this answer









$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
















5












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






share|cite|improve this answer









$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














5












5








5





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






share|cite|improve this answer









$endgroup$



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







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 14 at 12:18









David RicherbyDavid Richerby

68.4k15103194




68.4k15103194








  • 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$
    " 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




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




$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 NtoBbb 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)}: nin Bbb N}={epsilon, 1, 1111, 111111, 1111111111111, cdots},$$
which is undecidable.








share|cite|improve this answer









$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
















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 NtoBbb 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)}: nin Bbb N}={epsilon, 1, 1111, 111111, 1111111111111, cdots},$$
which is undecidable.








share|cite|improve this answer









$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














1












1








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 NtoBbb 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)}: nin Bbb N}={epsilon, 1, 1111, 111111, 1111111111111, cdots},$$
which is undecidable.








share|cite|improve this answer









$endgroup$



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 NtoBbb 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)}: nin Bbb N}={epsilon, 1, 1111, 111111, 1111111111111, cdots},$$
which is undecidable.









share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 14 at 18:33









Apass.JackApass.Jack

12.7k1939




12.7k1939












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


















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
















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




$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 $win L$ iff $w' in L'$..."






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Nitpicking here. Suppose $Lsubset {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
















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 $win L$ iff $w' in L'$..."






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Nitpicking here. Suppose $Lsubset {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














0












0








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 $win L$ iff $w' in L'$..."






share|cite|improve this answer











$endgroup$



$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 $win L$ iff $w' in L'$..."







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Feb 15 at 10:42

























answered Feb 14 at 17:15









Christoph BurschkaChristoph Burschka

1214




1214












  • $begingroup$
    Nitpicking here. Suppose $Lsubset {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


















  • $begingroup$
    Nitpicking here. Suppose $Lsubset {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
















$begingroup$
Nitpicking here. Suppose $Lsubset {0}^*$ is undecidable.Then $L'={epsilon}$ (or what?) is decidable.
$endgroup$
– Apass.Jack
Feb 14 at 18:47






$begingroup$
Nitpicking here. Suppose $Lsubset {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




$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


















draft saved

draft discarded




















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104320%2fis-the-infinite-language-unrecognizable-in-a-turing-machine%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Image
0 0 $begingroup$ Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments back to the class in a random fashion for grading. Each student receives one quiz and one homework assignment to grade. (a) What is the probability that every student receives someone else's quiz to grade, and someone else's homework to grade? (b) What is the probability that no student receives both their own quiz and their own homework assignment to grade? In this case, some students may receive their own quiz, and others may receive their own homework assignment. (c) Compute the limiting probability as n approaches infinity in each case. ...
Read more

Aardman Animations

Image
Aardman Animations, Ltd. Aardman Animations Tipo privada Atividade Animação em stop-motion , Animação em CGI Fundação 1972 Fundador(es) Peter Lord David Sproxton Sede Bristol, Inglaterra  Reino Unido Proprietário(s) Dreamworks Pessoas-chave Peter Lord David Sproxton Nick Park Divisões Aardman Features Aardman Digital Aardman Commercials Aardman Broadcast Aardman International Aardman Rights Aardman Effects Aardman 3-D Systems Aardman Nathan Love AardBoiled Website oficial aardman.com ...
Read more

Are they similar matrix

Image
0 $begingroup$ Do $begin{bmatrix} 0&i&0\0&0&1\0&0&0 end{bmatrix} $ and $begin{bmatrix} 0&0&0\-i&0&0\0&1&0 end{bmatrix} $ are similar.Is this True/false Clearly both are nilpotent and one is conjucate transpose of other but how to know if they are similar.i'm stuck. Please help me linear-algebra vector-spaces eigenvalues-eigenvectors generalizedeigenvector share | cite | improve this question edited Dec 10 '18 at 6:38 Vasanth Kris asked Dec 10 '18 at 6:19 ...
Read more