Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Andy Walker <anw@cuboid.co.uk>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows --- Semantic
 Property of Finite String
Date: Sat, 15 Mar 2025 10:08:20 +0000
Organization: Not very much
Lines: 28
Message-ID: <vr3jik$392v0$1@dont-email.me>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqs2n8$2knng$1@dont-email.me>
 <5429f6c8b8a8a79e06b4aeefe677cc54a2a636bf@i2pn2.org>
 <vqt9jp$2spcd$6@dont-email.me> <vqtag4$2t2hb$2@dont-email.me>
 <vqtgl0$2u7fo$1@dont-email.me>
 <924e22fc46d629b311b16a954dd0bed980a0a094@i2pn2.org>
 <vqvg7s$3s1qt$3@dont-email.me> <vqvgb4$3kfru$5@dont-email.me>
 <vqvi94$3tk5h$1@dont-email.me> <vr01sq$9741$1@dont-email.me>
 <0672fec6cb2a5c56fd674bbbb3d2b2101c8f295f@i2pn2.org>
 <vr185f$1aah4$1@dont-email.me> <87bju3jswc.fsf@nosuchdomain.example.com>
 <vr2d01$27fvs$1@dont-email.me> <vr2ju5$2deaa$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 15 Mar 2025 11:08:21 +0100 (CET)
Injection-Info: dont-email.me; posting-host="6e59f8192c6943d3155a73cdc6020c64";
	logging-data="3443680"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Q9RkvMMHtCez/0CBtJDy+"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:psWQsp+QCL5fN7HuOleQDQ22TAs=
In-Reply-To: <vr2ju5$2deaa$3@dont-email.me>
Content-Language: en-US

On 15/03/2025 01:08, olcott wrote:
> On 3/14/2025 6:09 PM, Andy Walker wrote:
>> On 14/03/2025 19:48, Keith Thompson wrote:
>>> [...] That would imply that [PO] could solve
>>> Goldbach's Conjecture, among other things, but I haven't seen him
>>> do so.
>>      Perhaps [just about] worth noting that a sufficiently long
>> [but not "infinite"] brute force attack on the GC [and many other
>> similar conjectures] would resolve the issue. 
> Not if GC is true and the proof cannot algorithmically
> compressed into a finite sequence of steps.

	You didn't read, or didn't understand, the rest of my article,
which explains that, indeed, only a finite number of steps is needed.
Read on before replying:

>>  Basically, if you
>> have a program [eg, TM] of size N by some suitable measure [eg, TM
>> states] then within [eg] BB(N) steps it must find the counter-example
>> [if there is one] or else there isn't one [and the GC is proven true],
>> where BB is the Busy Beaver function.  Of course, BB is uncomputable,
>> but that doesn't mean specific individual values are uncomputable,
>> just that there is no TM that computes it /in general/.

-- 
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/West