Is the infinite language unrecognizable in a Turing machine?
$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
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
$endgroup$
add a comment |
$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
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
$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
add a comment |
$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
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
$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
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
edited Feb 14 at 14:30
Andrew Raleigh
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
asked Feb 13 at 20:07
Andrew RaleighAndrew Raleigh
707
707
$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
add a comment |
$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
add a comment |
4 Answers
4
active
oldest
votes
$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$.
answered Feb 13 at 20:28
DraconisDraconis
5,792921
$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
|
show 4 more comments
$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).
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
$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
add a comment |
$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.
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
$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
add a comment |
$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'$..."
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
$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
add a comment |
Your Answer
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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$.
answered Feb 13 at 20:28
DraconisDraconis
5,792921
$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
|
show 4 more comments
$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$.
answered Feb 13 at 20:28
DraconisDraconis
5,792921
$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
|
show 4 more comments
$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$.
answered Feb 13 at 20:28
DraconisDraconis
5,792921
$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$.
answered Feb 13 at 20:28
DraconisDraconis
5,792921
answered Feb 13 at 20:28
DraconisDraconis
5,792921
answered Feb 13 at 20:28
DraconisDraconis
5,792921
answered Feb 13 at 20:28
DraconisDraconis
5,792921
5,792921
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
|
show 4 more comments
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
|
show 4 more comments
$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).
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
$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
add a comment |
$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).
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
$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
add a comment |
$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).
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
$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).
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
answered Feb 14 at 12:18
David RicherbyDavid Richerby
70.4k16107196
70.4k16107196
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
add a comment |
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
add a comment |
$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.
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
$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
add a comment |
$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.
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
$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
add a comment |
$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.
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
$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.
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
answered Feb 14 at 18:33
Apass.JackApass.Jack
14.3k1940
14.3k1940
$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
add a comment |
$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
add a comment |
$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'$..."
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
$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
add a comment |
$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'$..."
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
$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
add a comment |
$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'$..."
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
$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'$..."
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
edited Feb 15 at 10:42
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
answered Feb 14 at 17:15
Christoph BurschkaChristoph Burschka
1214
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
add a comment |
$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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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