Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












3












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










share|cite|improve this question









$endgroup$
















    3












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










    share|cite|improve this question









    $endgroup$














      3












      3








      3





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










      share|cite|improve this question









      $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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Feb 28 at 12:56









      StefanHStefanH

      805414




      805414




















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          This is a situation where coding is non-trivial. $mathcalC_T$ is a class of decidable languages. To make sense of $mathcalC_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 $mathcalC_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 mathbbN = mathcalC_T$. Note that this does not give us that $mathcalC_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcalC_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 $mathcalC_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.






          share|cite|improve this answer









          $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
            Feb 28 at 13:47







          • 4




            $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
            Feb 28 at 14:12






          • 4




            $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
            Feb 28 at 14:15


















          1












          $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 a TM which halts in $T(n)$ steps for each input of size $n$.
          $$

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






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
            $endgroup$
            – chi
            Feb 28 at 17:30










          • $begingroup$
            @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
            $endgroup$
            – StefanH
            Mar 1 at 13:17











          • $begingroup$
            So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
            $endgroup$
            – chi
            Mar 1 at 13:19






          • 1




            $begingroup$
            @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
            $endgroup$
            – StefanH
            Mar 1 at 13:30










          • $begingroup$
            Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
            $endgroup$
            – chi
            Mar 1 at 15:32










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









          3












          $begingroup$

          This is a situation where coding is non-trivial. $mathcalC_T$ is a class of decidable languages. To make sense of $mathcalC_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 $mathcalC_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 mathbbN = mathcalC_T$. Note that this does not give us that $mathcalC_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcalC_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 $mathcalC_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.






          share|cite|improve this answer









          $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
            Feb 28 at 13:47







          • 4




            $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
            Feb 28 at 14:12






          • 4




            $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
            Feb 28 at 14:15















          3












          $begingroup$

          This is a situation where coding is non-trivial. $mathcalC_T$ is a class of decidable languages. To make sense of $mathcalC_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 $mathcalC_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 mathbbN = mathcalC_T$. Note that this does not give us that $mathcalC_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcalC_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 $mathcalC_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.






          share|cite|improve this answer









          $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
            Feb 28 at 13:47







          • 4




            $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
            Feb 28 at 14:12






          • 4




            $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
            Feb 28 at 14:15













          3












          3








          3





          $begingroup$

          This is a situation where coding is non-trivial. $mathcalC_T$ is a class of decidable languages. To make sense of $mathcalC_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 $mathcalC_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 mathbbN = mathcalC_T$. Note that this does not give us that $mathcalC_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcalC_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 $mathcalC_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.






          share|cite|improve this answer









          $endgroup$



          This is a situation where coding is non-trivial. $mathcalC_T$ is a class of decidable languages. To make sense of $mathcalC_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 $mathcalC_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 mathbbN = mathcalC_T$. Note that this does not give us that $mathcalC_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $mathcalC_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 $mathcalC_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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Feb 28 at 13:33









          ArnoArno

          55116




          55116











          • $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
            Feb 28 at 13:47







          • 4




            $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
            Feb 28 at 14:12






          • 4




            $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
            Feb 28 at 14:15
















          • $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
            Feb 28 at 13:47







          • 4




            $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
            Feb 28 at 14:12






          • 4




            $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
            Feb 28 at 14:15















          $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
          Feb 28 at 13:47





          $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
          Feb 28 at 13:47





          4




          4




          $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
          Feb 28 at 14:12




          $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
          Feb 28 at 14:12




          4




          4




          $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
          Feb 28 at 14:15




          $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
          Feb 28 at 14:15











          1












          $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 a TM which halts in $T(n)$ steps for each input of size $n$.
          $$

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






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
            $endgroup$
            – chi
            Feb 28 at 17:30










          • $begingroup$
            @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
            $endgroup$
            – StefanH
            Mar 1 at 13:17











          • $begingroup$
            So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
            $endgroup$
            – chi
            Mar 1 at 13:19






          • 1




            $begingroup$
            @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
            $endgroup$
            – StefanH
            Mar 1 at 13:30










          • $begingroup$
            Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
            $endgroup$
            – chi
            Mar 1 at 15:32















          1












          $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 a TM which halts in $T(n)$ steps for each input of size $n$.
          $$

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






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
            $endgroup$
            – chi
            Feb 28 at 17:30










          • $begingroup$
            @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
            $endgroup$
            – StefanH
            Mar 1 at 13:17











          • $begingroup$
            So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
            $endgroup$
            – chi
            Mar 1 at 13:19






          • 1




            $begingroup$
            @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
            $endgroup$
            – StefanH
            Mar 1 at 13:30










          • $begingroup$
            Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
            $endgroup$
            – chi
            Mar 1 at 15:32













          1












          1








          1





          $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 a TM which halts in $T(n)$ steps for each input of size $n$.
          $$

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






          share|cite|improve this answer











          $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 a TM which halts in $T(n)$ steps for each input of size $n$.
          $$

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







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Mar 1 at 13:28

























          answered Feb 28 at 15:18









          StefanHStefanH

          805414




          805414











          • $begingroup$
            What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
            $endgroup$
            – chi
            Feb 28 at 17:30










          • $begingroup$
            @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
            $endgroup$
            – StefanH
            Mar 1 at 13:17











          • $begingroup$
            So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
            $endgroup$
            – chi
            Mar 1 at 13:19






          • 1




            $begingroup$
            @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
            $endgroup$
            – StefanH
            Mar 1 at 13:30










          • $begingroup$
            Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
            $endgroup$
            – chi
            Mar 1 at 15:32
















          • $begingroup$
            What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
            $endgroup$
            – chi
            Feb 28 at 17:30










          • $begingroup$
            @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
            $endgroup$
            – StefanH
            Mar 1 at 13:17











          • $begingroup$
            So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
            $endgroup$
            – chi
            Mar 1 at 13:19






          • 1




            $begingroup$
            @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
            $endgroup$
            – StefanH
            Mar 1 at 13:30










          • $begingroup$
            Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
            $endgroup$
            – chi
            Mar 1 at 15:32















          $begingroup$
          What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
          $endgroup$
          – chi
          Feb 28 at 17:30




          $begingroup$
          What is $n$ in $T(n)$ here? Anyway, the set $mathcal A$ looks decidable to me, since a TM in $T(n)$ steps can only read $T(n)$ symbols from the tape, so there's only a finite number of inputs to try, for a given number of steps.
          $endgroup$
          – chi
          Feb 28 at 17:30












          $begingroup$
          @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
          $endgroup$
          – StefanH
          Mar 1 at 13:17





          $begingroup$
          @chi Thanks for your feedback, $T : mathbb N to mathbb N$ is a function and $n$ its argument... is your objection still valid then? As $T(n)$ varies with the input (of size $n$).
          $endgroup$
          – StefanH
          Mar 1 at 13:17













          $begingroup$
          So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
          $endgroup$
          – chi
          Mar 1 at 13:19




          $begingroup$
          So $mathcal A$ actually depends on $T$ and $n$, and $n$ which are completely independent from $M$? I think my objection still stands, then.
          $endgroup$
          – chi
          Mar 1 at 13:19




          1




          1




          $begingroup$
          @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
          $endgroup$
          – StefanH
          Mar 1 at 13:30




          $begingroup$
          @chi I mean $M$ has to halt in $T(|w|)$ steps for each input $w$, so $n$ is not fixed in advance but depends on the input size $M$ receives. Okay?
          $endgroup$
          – StefanH
          Mar 1 at 13:30












          $begingroup$
          Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
          $endgroup$
          – chi
          Mar 1 at 15:32




          $begingroup$
          Ah, right, I see now. I now agree: $mathcal A$ looks coRE only.
          $endgroup$
          – chi
          Mar 1 at 15:32

















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





















































          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

          How to check contact read email or not when send email to Individual?

          Displaying single band from multi-band raster using QGIS

          How many registers does an x86_64 CPU actually have?