Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: How to prove this TM problem?
Date: Thu, 24 Oct 2024 22:57:46 +0800
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <e2bb8f2c1af6de5303a2ac020e21e3e51f992a9f.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Thu, 24 Oct 2024 16:57:47 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ea8689f96dacdd225dada9e3e6487b72";
	logging-data="2817103"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+DIwYzfzm8/PczlrHqvxSS"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:FoDB6cjA8F4LkC2waI2UUpJUWko=
Bytes: 1374

U=3D {m| m is a Turing machine that computes a decision problem }

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

Prop: Let S(n)=3D{m| m=E2=88=88U, size(m)=3Dn }.
          Q(n)=3D{q| q is problem that can be computed by a TM in S(n) }
      Q(a)=E2=8A=82Q(b) iff a<b

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

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