Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable functions
Date: Tue, 25 Mar 2025 11:09:36 +0200
Organization: -
Lines: 39
Message-ID: <vrtrsg$30498$1@dont-email.me>
References: <vr1shq$1qopn$1@dont-email.me> <vr9elt$bv13$2@dont-email.me> <vr9jpt$gave$2@dont-email.me> <vr9lj6$j0f0$2@dont-email.me> <vr9qu8$m4cu$2@dont-email.me> <vr9ttl$q57o$1@dont-email.me> <vr9u5m$q57o$2@dont-email.me> <vrbckn$23f4t$1@dont-email.me> <vrbtiq$2j07c$2@dont-email.me> <vrc3ud$2p461$1@dont-email.me> <vrc4nu$2m36k$5@dont-email.me> <vrkc2m$24ft6$1@dont-email.me> <vrkdij$25f9f$3@dont-email.me> <vrlt36$3haib$1@dont-email.me> <vrn237$im1e$1@dont-email.me> <vrn67b$md49$1@dont-email.me> <cb974817db8e02049daa5604d725300154e33ad1@i2pn2.org> <vrps14$35a4m$2@dont-email.me> <eab11e8806c669d296bff986870bdc6abdbb2fef@i2pn2.org> <vrqicu$3s258$1@dont-email.me> <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org> <vrrs79$11a56$7@dont-email.me> <vrrsta$tdm5$1@dont-email.me> <vrs264$1a43i$1@dont-email.me> <vrs54q$1d1o2$1@dont-email.me> <vrse90$1jr8u$1@dont-email.me> <vrsk13$1q39o$1@dont-email.me> <vrsn62$1rblu$2@dont-email.me> <vrsnhu$1q39o$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 25 Mar 2025 10:09:36 +0100 (CET)
Injection-Info: dont-email.me; posting-host="2f0cf999c00fadfadc7508b49d8fc2da";
	logging-data="3150120"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19No6/4N2tVBZhAndlgM2Sp"
User-Agent: Unison/2.2
Cancel-Lock: sha1:r53RrbkXvAZY1gc/qcxf+ZQ4Db0=
Bytes: 3322

On 2025-03-24 22:49:34 +0000, André G. Isaak said:

> On 2025-03-24 16:43, olcott wrote:
> 
>>> Computable functions don't have inputs. They have domains. Turing 
>>> machines have inputs.p
>>> 
>> 
>> Maybe when pure math objects. In every model of
>> computation they seem to always have inputs.
>> https://en.wikipedia.org/wiki/Computable_function
> 
> Computable functions *are* pure math objects. You seem to want to 
> conflate them with C functions, but that is not the case.
> 
> The crucial point is that the domains of computable functions are *not* 
> restricted to strings, even if the inputs to Turing Machines are.
> 
>>> While the inputs to TMs are restricted to strings, there is no such 
>>> such restriction on computable functions.
>> 
>>> The vast majority of computable functions of interest do *not* have 
>>> strings as their domains, yet they remain computable functions (a 
>>> simple example would be the parity function which maps NATURAL NUMBERS 
>>> (not strings) to yes/no values.)
>> 
>> Since there is a bijection between natural numbers
>> and strings of decimal digits your qualification
>> seems vacuous.
> 
> There is not a bijection between natural numbers and strings.

There is a bijection between natural numbers and strings of any any finite
or countable string. For every such alphabeth the set of strings is
countable. Every countable set has a bijection with natural numbers.

-- 
Mikko