How to prove this TM problem?

Liste des GroupesRevenir à theory 
Sujet : How to prove this TM problem?
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theory
Date : 24. Oct 2024, 15:57:46
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <e2bb8f2c1af6de5303a2ac020e21e3e51f992a9f.camel@gmail.com>
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
U= {m| m is a Turing machine that computes a decision problem }

size(m)::= Length of TM description (standardized) of the TM m.

Prop: Let S(n)={m| m∈U, size(m)=n }.
          Q(n)={q| q is problem that can be computed by a TM in S(n) }
      Q(a)⊂Q(b) iff a<b

I.e. The set of problems that larger TM solve cannot be (all) solved by smaller ones.

Prop is easy to comprehend, but how to prove it?
I have many problems hinge on this proposition.



Date Sujet#  Auteur
24 Oct 24 o How to prove this TM problem?1wij

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal