Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Turing Machine computable functions MUST apply finite string transformations to inputs Date: Wed, 30 Apr 2025 23:55:01 -0400 Organization: A noiseless patient Spider Lines: 113 Message-ID: References: <87cyd5182l.fsf@nosuchdomain.example.com> <991dde3a60e1485815b789520c7149e7842d18f2@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 01 May 2025 05:55:01 +0200 (CEST) Injection-Info: dont-email.me; posting-host="7f5b81f1e3771b63e4016ac43992f172"; logging-data="1489558"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18+Nq5ynmRDGHxirmicPp9x" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:+xMJGt/VPiBL/w4Qpa+8znRjPA8= In-Reply-To: Content-Language: en-US On 4/30/2025 11:50 PM, olcott wrote: > On 4/30/2025 7:17 PM, André G. Isaak wrote: >> On 2025-04-30 16:09, olcott wrote: >>> On 4/30/2025 2:55 PM, dbush wrote: >>>> On 4/30/2025 1:32 PM, olcott wrote: >>>>> On 4/30/2025 11:11 AM, Richard Heathfield wrote: >>>>>> On 30/04/2025 16:44, joes wrote: >>>>>>> Am Wed, 30 Apr 2025 10:09:45 -0500 schrieb olcott: >>>>>>>> On 4/29/2025 5:01 AM, Mikko wrote: >>>>>>> >>>>>>>>> Irrelevant. There is sufficient agreement what Turing machines >>>>>>>>> are. >>>>>>>> >>>>>>>> Turing machine computable functions must apply finite string >>>>>>>> transformation rues to inputs to derive outputs. >>>>>>>> >>>>>>>> This is not a function that computes the sum(3,2): >>>>>>>> int sum(int x, int y) { return 5; } >>>>>>> Yes it is, for all inputs. >>>>>> >>>>>> Not much of a computation, though, is it? >>>>>> >>>>> >>>>> It IS NOT a Turing Computable function >>>> >>>> Lying by misuse of terms. >>>> >>>> A turing computable function is a mapping for which an algorithm >>>> exists to compute it, not the algorithm itself. >>>> >>>> Further use of "turing computable function" when what is meant is >>>> "algorithm" will result in the former being replaced with the later >>>> in future responses to your posts to make it clear what you are >>>> actually talking about. >>>> >>>> >>>>> because it does not ever apply any finite >>>>> string transformation  rules to its inputs. >>>> >>>> Sure it does.  It computes the mapping of all pairs of integers to >>>> the number 5. >>>> >>> >>> int sum(int x, int y) { return 5; } >>> Does not apply transformations to its inputs >>> to derive its outputs thus is no kind of computable >>> function not even for sum(2,3). >> >> You are still hopelessly confused about your terminology. >> >> Computable functions are a subset of mathematical functions, and >> mathematical functions are *not* the same thing as C functions. >> Functions do not apply "transformations". They are simply mappings, >> and a functions which maps every pair of natural numbers to 5 is a >> perfectly legitimate, albeit not very interesting, function. >> >> What makes this function a *computable function* is that fact that it >> is possible to construct a C function (or a Turing Machine, or some >> other type of algorithm) such as int foo(int x, int y) {return 5;} >> which computes that particular function; but the C function and the >> computable function it computes are entirely separate entities. > > computes the sum of two integers > by transforming the inputs into an output. > int sum(int x, int y) { return x + y; } > > Computes no function because it ignores its inputs. > int sum(int x, int y) { return 5; } False. It computes this function: For all integers X and Y: (X,Y) maps to 5 > >> [I won't call that function 'sum()' because that would be misleading, >> but the the *name* assigned to a C function has no necessary relation >> to the function it computes. It's good programming practice to give >> functions descriptive names but nothing in the C standard requires it). >> >> You keep conflating C functions/Turing Machines with computable >> functions and as a result come across as completely ignorant about the >> topic you purport to be discussing. No C function or Turing Machine is >> a computable function. They are ways of expressing algorithms. >> >> André >> > > The complete ignorance is to expect HHH(DD) > to report on DD(DD). It is expected when we start with the assumption that the following requirements can be satisfied and HHH satisfies them. Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as with input Y: A solution to the halting problem is an algorithm H that computes the following mapping: (,Y) maps to 1 if and only if X(Y) halts when executed directly (,Y) maps to 0 if and only if X(Y) does not halt when executed directly When we reach a contradiction, that proves the assumption that the above requirements can be met is false, as shown by Linz and as you have *explicitly* agreed with.