| Deutsch English Français Italiano |
|
<47d52c4babb83d32286f6bf597b415151d3e4fda.camel@gmail.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!weretis.net!feeder9.news.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 06:55:51 +0800 Organization: A noiseless patient Spider Lines: 23 Message-ID: <47d52c4babb83d32286f6bf597b415151d3e4fda.camel@gmail.com> References: <e59d06e61850db2c77d1a784abce13dc84067079.camel@gmail.com> <19b48c13e1abe0c0c68ece8114535d43a771cd3c.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 00:55:52 +0200 (CEST) Injection-Info: dont-email.me; posting-host="356615fa2e3e10e4de8b1fb8357c2248"; logging-data="852859"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+vCMlJohhOYegRWjVHrOD3" User-Agent: Evolution 3.50.2 (3.50.2-1.fc39) Cancel-Lock: sha1:dxALWk7PtXmUdjohJXFYTwo2Glc= In-Reply-To: <19b48c13e1abe0c0c68ece8114535d43a771cd3c.camel@gmail.com> Bytes: 1949 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). B= ut if we > > restrict the condition a little bit: Does there exists a decision funct= ion h, h > > determines whether or not an arbitrary function void f() (given as the = argument > > of h) terminates or not (h,f=E2=88=88O(2^N)) ? IOW, h(f)=3D=3Dtrue iff = f() terminates. >=20 > Sorry, too quick in rephrasing the real problem. I should fix this latter= .. >=20 Correction: Does there exist a O(2^N) decision function sat, sat terminates whether or = not a O(2^N) function bool f() (given as the argument of sat) returns true or n= ot? IOW, sat(f)=3D=3Dtrue iff f()=3D=3Dtrue