Path: ...!feeder1.cambriumusenet.nl!feed.tweak.nl!217.73.144.44.MISMATCH!feeder.ecngs.de!ecngs!feeder2.ecngs.de!168.119.53.7.MISMATCH!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: Another Halting Problem Question (very difficult)
Date: Wed, 29 May 2024 08:31:29 +0800
Organization: A noiseless patient Spider
Lines: 34
Message-ID: <1f231ededa977e799945496518d7aa8e2f7efc4a.camel@gmail.com>
References: <e59d06e61850db2c77d1a784abce13dc84067079.camel@gmail.com>
	 <19b48c13e1abe0c0c68ece8114535d43a771cd3c.camel@gmail.com>
	 <47d52c4babb83d32286f6bf597b415151d3e4fda.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Wed, 29 May 2024 02:31:30 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="356615fa2e3e10e4de8b1fb8357c2248";
	logging-data="878834"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19C4MvV8x8q1bZYOGYBRJJw"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:PP3iY+g7LrPZPif9iXVD9kBqAOI=
In-Reply-To: <47d52c4babb83d32286f6bf597b415151d3e4fda.camel@gmail.com>
Bytes: 2465

On Wed, 2024-05-29 at 06:55 +0800, wij wrote:
> On Wed, 2024-05-29 at 06:20 +0800, wij wrote:
> > On Wed, 2024-05-29 at 05:37 +0800, wij wrote:
> > > Everybody knows the Halting Problem is undecidable (liars also know).=
 But if we
> > > restrict the condition a little bit: Does there exists a decision fun=
ction h, h
> > > determines whether or not an arbitrary function void f() (given as th=
e argument
> > > of h) terminates or not (h,f=E2=88=88O(2^N)) ? IOW, h(f)=3D=3Dtrue if=
f f() terminates.
> >=20
> > Sorry, too quick in rephrasing the real problem. I should fix this latt=
er.
> >=20
>=20
> Correction:
> Does there exist a O(2^N) decision function sat, sat terminates whether o=
r not
> a O(2^N) function bool f() (given as the argument of sat) returns true or=
 not?
> IOW, sat(f)=3D=3Dtrue iff f()=3D=3Dtrue
>=20
>=20

Revision:
Does there exist a decision function sat that determines whether or not a
terminating function bool f() (given as the argument of sat) returns true o=
r
not? IOW, sat(f)=3D=3Dtrue iff f()=3D=3Dtrue.

Is Rice's theorem (or GUR if you like) refuted?