Is the set of language decidable by some Turing machine computing in some given computable time bound...
Advice for a new journal editor
Is boss over stepping boundary/micromanaging?
How to limit sight distance to 1 KM
Is it possible to grant users sftp access without shell access? If yes, how is it implemented?
Using only 1s, make 29 with the minimum number of digits
What's a good word to describe a public place that looks like it wouldn't be rough?
Early credit roll before the end of the film
Dilemma of explaining to interviewer that he is the reason for declining second interview
Bash Script Function Return True-False
Why publish a research paper when a blog post or a lecture slide can have more citation count than a journal paper?
LuaTex and em dashes
Can I write a book of my D&D game?
Publishing research using outdated methods
A title for a history book
What is causing the chain skip after chain replacement?
Graph with overlapping labels
How to make ice magic work from a scientific point of view?
Consequences of lack of rigour
How to prevent cleaner from hanging my lock screen in Ubuntu 16.04
What is the wife of a henpecked husband called?
Transpose a matrix and parenthesis
Why are these T-SQL jobs from different SQL Server instances executed on the same instance (AlwaysOn Availability Groups)
Cat is tipping over bed-side lamps during the night
Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?Language comprising of Turing machine encodingsDecidability of the language that accepts a universal turing machineIs it possible to ever define $L(M)$ of a given Turing Machine, $M$?Proving that a language of Turing machine descriptions is/is not Turing recognizableturing machine decidability languageGiven a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?Is the complement of the Turing machine equality language not recursively enumerable as well?Is the language below not decidable , if yes , it is then R.E ?Whether language of all turing machines is decidable or undecidable or semi-decidable?
$begingroup$
Let $T : mathbb N to mathbb N$ be some computable function. Then by $mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a ${0,1,}$-sequence could be considered a subset of $mathbb N$, and going from to $mathbb N$ to $Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $mathcal C_T$ some machine is enumerated for it.
But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:
Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $Sigma^{ast} = {w_1, w_2, w_3, ldots }$
and $c : mathbb N to mathbb N times mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.
A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).
Hence it accepts the complement of $mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.
Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...
turing-machines computability undecidability decision-problem
$endgroup$
add a comment |
$begingroup$
Let $T : mathbb N to mathbb N$ be some computable function. Then by $mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a ${0,1,}$-sequence could be considered a subset of $mathbb N$, and going from to $mathbb N$ to $Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $mathcal C_T$ some machine is enumerated for it.
But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:
Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $Sigma^{ast} = {w_1, w_2, w_3, ldots }$
and $c : mathbb N to mathbb N times mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.
A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).
Hence it accepts the complement of $mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.
Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...
turing-machines computability undecidability decision-problem
$endgroup$
add a comment |
$begingroup$
Let $T : mathbb N to mathbb N$ be some computable function. Then by $mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a ${0,1,}$-sequence could be considered a subset of $mathbb N$, and going from to $mathbb N$ to $Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $mathcal C_T$ some machine is enumerated for it.
But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:
Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $Sigma^{ast} = {w_1, w_2, w_3, ldots }$
and $c : mathbb N to mathbb N times mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.
A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).
Hence it accepts the complement of $mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.
Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...
turing-machines computability undecidability decision-problem
$endgroup$
Let $T : mathbb N to mathbb N$ be some computable function. Then by $mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a ${0,1,}$-sequence could be considered a subset of $mathbb N$, and going from to $mathbb N$ to $Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $mathcal C_T$ some machine is enumerated for it.
But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:
Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $Sigma^{ast} = {w_1, w_2, w_3, ldots }$
and $c : mathbb N to mathbb N times mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.
A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).
Hence it accepts the complement of $mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.
Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...
turing-machines computability undecidability decision-problem
turing-machines computability undecidability decision-problem
asked 3 hours ago
StefanHStefanH
731414
731414
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is a situation where coding is non-trivial. $mathcal{C}_T$ is a class of decidable languages. To make sense of $mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.
So what does it mean for $mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that ${L(M_i) mid i in mathbb{N}} = mathcal{C}_T$. Note that this does not give us that $mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcal{C}_T$.
The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.
Furthermore, the complement of $mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.
$endgroup$
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
add a comment |
$begingroup$
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.
Define
$$
mathcal A = { M mid mbox{ $M$ is the code of some TM which halts in $T(n)$ steps for each input }}.
$$
Then $mathcal C_T = { L(M) : M in mathcal A }$. As shown in my post the complement of the set $mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $mathcal A$ itself (where for $mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $mathcal C_L$ (strictly we have to show that $mathcal C_L$ is non-trivial first, but this I take for granted now).
Note by the way that the complement of $mathcal C_T$ is not even enumerable. But what we mean when we say $mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set ${ L(M) mid M mbox{ is some TM } }$.
$endgroup$
add a comment |
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
});
}
});
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%2f104955%2fis-the-set-of-language-decidable-by-some-turing-machine-computing-in-some-given%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is a situation where coding is non-trivial. $mathcal{C}_T$ is a class of decidable languages. To make sense of $mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.
So what does it mean for $mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that ${L(M_i) mid i in mathbb{N}} = mathcal{C}_T$. Note that this does not give us that $mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcal{C}_T$.
The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.
Furthermore, the complement of $mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.
$endgroup$
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
add a comment |
$begingroup$
This is a situation where coding is non-trivial. $mathcal{C}_T$ is a class of decidable languages. To make sense of $mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.
So what does it mean for $mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that ${L(M_i) mid i in mathbb{N}} = mathcal{C}_T$. Note that this does not give us that $mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcal{C}_T$.
The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.
Furthermore, the complement of $mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.
$endgroup$
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
add a comment |
$begingroup$
This is a situation where coding is non-trivial. $mathcal{C}_T$ is a class of decidable languages. To make sense of $mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.
So what does it mean for $mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that ${L(M_i) mid i in mathbb{N}} = mathcal{C}_T$. Note that this does not give us that $mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcal{C}_T$.
The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.
Furthermore, the complement of $mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.
$endgroup$
This is a situation where coding is non-trivial. $mathcal{C}_T$ is a class of decidable languages. To make sense of $mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.
So what does it mean for $mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that ${L(M_i) mid i in mathbb{N}} = mathcal{C}_T$. Note that this does not give us that $mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcal{C}_T$.
The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.
Furthermore, the complement of $mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.
answered 2 hours ago
ArnoArno
51115
51115
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
add a comment |
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
$begingroup$
Thanks, I do not get your 3rd paragraph. What is the space of pf decidable languages, what you mean by decidable equality?? Could you please expand on that...
$endgroup$
– StefanH
2 hours ago
3
3
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
$begingroup$
@StefanH The point is: when we deal with sets of natural numbers (or words), we can use the standard computability notions of (semi) decidability. When instead we deal with sets of sets of natural numbers, we need to be careful with the coding. The space of decidable language is the set of all decidable languages, so it is a set-of-sets (of words). Here we need to represent each language with a TM, a "code" for that -- however there might be many codes for the same language! This makes the problem "given two languages (their codes) are those the same?" non trivial.
$endgroup$
– chi
2 hours ago
3
3
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
$begingroup$
@StefanH Decidable equality would mean that, given two codes we can decide whether they represent the same thing. If codes are for languages, that would mean that given $i,j$ we can decide whether $L(M_i)=L(M_j)$ -- which is unfeasible. So: natural numbers, strings, rational numbers, (finite) trees / graphs, ... have decidable equality. Computable real numbers, decidable sets, ... have undecidable equality.
$endgroup$
– chi
2 hours ago
add a comment |
$begingroup$
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.
Define
$$
mathcal A = { M mid mbox{ $M$ is the code of some TM which halts in $T(n)$ steps for each input }}.
$$
Then $mathcal C_T = { L(M) : M in mathcal A }$. As shown in my post the complement of the set $mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $mathcal A$ itself (where for $mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $mathcal C_L$ (strictly we have to show that $mathcal C_L$ is non-trivial first, but this I take for granted now).
Note by the way that the complement of $mathcal C_T$ is not even enumerable. But what we mean when we say $mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set ${ L(M) mid M mbox{ is some TM } }$.
$endgroup$
add a comment |
$begingroup$
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.
Define
$$
mathcal A = { M mid mbox{ $M$ is the code of some TM which halts in $T(n)$ steps for each input }}.
$$
Then $mathcal C_T = { L(M) : M in mathcal A }$. As shown in my post the complement of the set $mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $mathcal A$ itself (where for $mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $mathcal C_L$ (strictly we have to show that $mathcal C_L$ is non-trivial first, but this I take for granted now).
Note by the way that the complement of $mathcal C_T$ is not even enumerable. But what we mean when we say $mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set ${ L(M) mid M mbox{ is some TM } }$.
$endgroup$
add a comment |
$begingroup$
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.
Define
$$
mathcal A = { M mid mbox{ $M$ is the code of some TM which halts in $T(n)$ steps for each input }}.
$$
Then $mathcal C_T = { L(M) : M in mathcal A }$. As shown in my post the complement of the set $mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $mathcal A$ itself (where for $mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $mathcal C_L$ (strictly we have to show that $mathcal C_L$ is non-trivial first, but this I take for granted now).
Note by the way that the complement of $mathcal C_T$ is not even enumerable. But what we mean when we say $mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set ${ L(M) mid M mbox{ is some TM } }$.
$endgroup$
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.
Define
$$
mathcal A = { M mid mbox{ $M$ is the code of some TM which halts in $T(n)$ steps for each input }}.
$$
Then $mathcal C_T = { L(M) : M in mathcal A }$. As shown in my post the complement of the set $mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $mathcal A$ itself (where for $mathcal C_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $mathcal C_L$ (strictly we have to show that $mathcal C_L$ is non-trivial first, but this I take for granted now).
Note by the way that the complement of $mathcal C_T$ is not even enumerable. But what we mean when we say $mathcal C_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set ${ L(M) mid M mbox{ is some TM } }$.
edited 51 mins ago
answered 58 mins ago
StefanHStefanH
731414
731414
add a comment |
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%2f104955%2fis-the-set-of-language-decidable-by-some-turing-machine-computing-in-some-given%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