Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: How computable functions actually work. (was Flibble)
Date: Tue, 22 Apr 2025 22:33:11 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <c56984842cd8193343404c51c965e22d2f245c52@i2pn2.org>
References: <vu89uf$dqtf$1@dont-email.me> <a7ONP.1086929$B61.895665@fx02.ams4>
 <vu93el$dp4v$1@dont-email.me> <vu94l0$1h90v$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 23 Apr 2025 02:34:22 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1482570"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vu94l0$1h90v$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US

On 4/22/25 6:19 PM, olcott wrote:
> On 4/22/2025 4:58 PM, Andy Walker wrote:
>> On 22/04/2025 15:57, Mr Flibble wrote:
>>> On Tue, 22 Apr 2025 15:43:27 +0100, Andy Walker wrote:
>>>> The "real" Mr Flibble is a malevolent penguin.  I wonder why
>>>> contributors take him so seriously?  If you want to debate with a
>>>> penguin, that's your prerogative, but to me it makes more sense to add
>>>> several pinches of salt and smile or groan as appropriate to everything
>>>> he writes.  He has a knack for writing things that are just about
>>>> plausible, which is enviable, but one response to anything interesting
>>>> is surely enough?
>>> Mr Flibble is very cross.
>>
>>      He shouldn't be.  As hinted above, being able to write successful
>> satire is a rare skill.  But it loses its point if too many people take
>> it seriously.
>>
> 
> Flibble <is> factually correct.
> 
> All computation is defined to be represented as finite string
> transformations to finite strings.

Except you are doing the logic backward.

> 
> This <is> how Turing Machine computable functions actually work.
> Outputs are forced to correspond to inputs when finite string
> transformation rules are applied to inputs to derive outputs.

And you need to know that the function *IS* computable to use that.

What the machine actually produces will be computable.

What the machine is SUPPOSED to produce might not be.

> 
>     a function is computable if there exists an algorithm
>     that can do the job of the function, i.e. given an input
>     of the function domain it can return the corresponding
>     output. https://en.wikipedia.org/wiki/Computable_function

Which says if a machine exists, it is conputable.

The machine does not need to exist.

This seems to be a flaw in your logic, you seem to think there is a 
Truth Faerie that can magically make the impossible happen.

> 
> On Turing Machines inputs <are> finite strings, and
> finite string transformation rules <are> applied to
> these finite strings to derive corresponding outputs.

Yes, so the results can only BE what is computable, but as pointed out, 
the correct answer need not be.

> 
> People here stupidly assume that the outputs are not
> required to correspond to the inputs. That comes from
> learn-by-rote with zero depth of understanding.
> 

The outputs DO need to correspond to the input, but not necessarily by a 
computable transform.

That only exists if the function is, in fact, computable.

Nearly all "random" functions will not be, by a simple counting 
argument, There are more functions/mapping (Aleph-1) that can be asked 
for than machines (Aleph-0) to do the mapping. Therefore only a 
infintisimal fraction of all possible mappings are in fact computable.

Now, when we limit ourselves to mapping that have a use, it seems we 
find a lot that do have a mapping, but not all.

There is no computation that can compute for *ALL* possible programs, if 
that progran will halt when run. Turing proves that by showing for every 
possible decider that we might think can do it, that we can make a 
program for it to decide on that it will get wrong.

Thus the mapping must be uncomputable.