Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Proof2: =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= is released
Date: Tue, 18 Mar 2025 18:58:36 +0800
Organization: A noiseless patient Spider
Lines: 34
Message-ID: <52d8d45d0db77680236c09bb395148d8803f7f17.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Tue, 18 Mar 2025 11:58:37 +0100 (CET)
Injection-Info: dont-email.me; posting-host="ce5e8c882daf6be7d69ac6d35bd5687f";
	logging-data="2474143"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/7oI05rAY/bHmj8WpgZF3j"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:juI38ACR4Jkeh+sSLa1AO4MGuRE=
Bytes: 2352

This =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 proof is the shortest one and eas=
y to understand

https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow=
nload
....
+--------------+
| Proof2: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 |
+--------------+
STM::=3D Turing machine represented by string {0,1}* string
Num(x)::=3D Function that maps {0,1}* to natural numbers

 Let s=E2=88=88STM, s:STM->{0,1}. s is a function that computes a Turing ma=
chine
 decision function in Ptime and is defined as follows:

   s(f)=3D1 if =E2=88=83c=E2=88=88<=3DNum(f), f(c)=3D1.

 Therefore, Problem(s)=E2=88=88=E2=84=95=E2=84=99 (the problem solved by s =
is =E2=84=95=E2=84=99 problem)
 The proof of this assertion is quite straightforward and trivial, so it is
 omitted. Doubts about whether certain natural numbers are legal Turing
 Machines are not a problem, because the definition of =E2=84=95=E2=84=99 d=
oes not consider
 (and can handle) this situation.

 Assume that Problem(s)=E2=88=88=E2=84=99 holds, then by definition
   s(s)=3D1 if =E2=88=83c=E2=88=88<=3DNum(s), s(c)=3D1.
 But when c=3DNum(s), there will be a self-referential situation where
   s(s)=3D1 if s(s)=3D1 (similar to the undecidable situation of the haltin=
g
 problem). Therefore, the assumption that =E2=84=99=3D=E2=84=95=E2=84=99 do=
es not hold, that is, =E2=84=99=E2=89=A0=E2=84=95=E2=84=99.