Warning: mysqli::__construct(): (HY000/1203): User howardkn already has more than 'max_user_connections' active connections in D:\Inetpub\vhosts\howardknight.net\al.howardknight.net\includes\artfuncs.php on line 21
Failed to connect to MySQL: (1203) User howardkn already has more than 'max_user_connections' active connectionsPath: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Peano Axioms anchored in First Grade Arithmetic on ASCII Digit String pairs Date: Fri, 25 Oct 2024 08:31:16 -0500 Organization: A noiseless patient Spider Lines: 105 Message-ID: References: <647fe917c6bc0cfc78083ccf927fe280acdf2f9d@i2pn2.org> <522ecce215e636ddb7c9a1f75bff1ba466604cc5@i2pn2.org> <87634d01e18903c744d109aaca3a20b9ce4278bb@i2pn2.org> <592109c757262c48aaca517a829ea1867913316b@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 25 Oct 2024 15:31:17 +0200 (CEST) Injection-Info: dont-email.me; posting-host="7cff08f8c76bdb8ebdc0a44831f3107c"; logging-data="3361479"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19geJ4nmQ/vMT41t6M4h9lw" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:HB6C5Rl+WkWqFmKTpEl9ggRWgnY= X-Antivirus: Norton (VPS 241025-2, 10/25/2024), Outbound message Content-Language: en-US In-Reply-To: X-Antivirus-Status: Clean Bytes: 6742 On 10/25/2024 3:01 AM, Mikko wrote: > On 2024-10-24 14:28:35 +0000, olcott said: > >> On 10/24/2024 8:51 AM, Mikko wrote: >>> On 2024-10-23 13:15:00 +0000, olcott said: >>> >>>> On 10/23/2024 2:28 AM, Mikko wrote: >>>>> On 2024-10-22 14:02:01 +0000, olcott said: >>>>> >>>>>> On 10/22/2024 2:13 AM, Mikko wrote: >>>>>>> On 2024-10-21 13:52:28 +0000, olcott said: >>>>>>> >>>>>>>> On 10/21/2024 3:41 AM, Mikko wrote: >>>>>>>>> On 2024-10-20 15:32:45 +0000, olcott said: >>>>>>>>> >>>>>>>>>> The actual barest essence for formal systems and computations >>>>>>>>>> is finite string transformation rules applied to finite strings. >>>>>>>>> >>>>>>>>> Before you can start from that you need a formal theory that >>>>>>>>> can be interpreted as a theory of finite strings. >>>>>>>> >>>>>>>> Not at all. The only theory needed are the operations >>>>>>>> that can be performed on finite strings: >>>>>>>> concatenation, substring, relational operator ... >>>>>>> >>>>>>> You may try with an informal foundation but you need to make sure >>>>>>> that it is sufficicently well defined and that is easier with a >>>>>>> formal theory. >>>>>>> >>>>>>>> The minimal complete theory that I can think of computes >>>>>>>> the sum of pairs of ASCII digit strings. >>>>>>> >>>>>>> That is easily extended to Peano arithmetic. >>>>>>> >>>>>>> As a bottom layer you need some sort of logic. There must be >>>>>>> unambifuous >>>>>>> rules about syntax and inference. >>>>>>> >>>>>> >>>>>> I already wrote this in C a long time ago. >>>>>> It simply computes the sum the same way >>>>>> that a first grader would compute the sum. >>>>>> >>>>>> I have no idea how the first grade arithmetic >>>>>> algorithm could be extended to PA. >>>>> >>>>> Basically you define that the successor of X is X + 1. The only >>>>> primitive function of Peano arithmetic is the successor. Addition >>>>> and multiplication are recursively defined from the successor >>>>> function. Equality is often included in the underlying logic but >>>>> can be defined recursively from the successor function and the >>>>> order relation is defined similarly. >>>>> >>>>> Anyway, the details are not important, only that it can be done. >>>>> >>>> >>>> First grade arithmetic can define a successor function >>>> by merely applying first grade arithmetic to the pair >>>> of ASCII digits strings of [0-1]+ and "1". >>>> https://en.wikipedia.org/wiki/Peano_axioms >>>> >>>> The first incompleteness theorem states that no consistent system of >>>> axioms whose theorems can be listed by an effective procedure (i.e. >>>> an algorithm) is capable of proving all truths about the arithmetic >>>> of natural numbers. For any such consistent formal system, there >>>> will always be statements about natural numbers that are true, but >>>> that are unprovable within the system. >>>> https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems >>>> >>>> When we boil this down to its first-grade arithmetic foundation >>>> this would seem to mean that there are some cases where the >>>> sum of a pair of ASCII digit strings cannot be computed. >>> >>> No, it does not. Incompleteness theorem does not apply to artihmetic >>> that only has addition but not multiplication. >>> >>> The incompleteness theorem is about theories that have quantifiers. >>> A specific arithmetic expression (i.e, with no variables of any kind) >>> always has a well defined value. >>> >> >> So lets goes the next step and add multiplication to the algorithm: >> (just like first grade arithmetic we perform multiplication >> on arbitrary length ASCII digit strings just like someone would >> do with pencil and paper). >> >> Incompleteness cannot be defined. until we add variables and >> quantification: There exists an X such that X * 11 = 132. >> Every detail of every step until we get G is unprovable in F. > > Incompleteness is easier to define if you also add the power operator > to the arithmetic. Otherwise the expressions of provability and > incompleteness are more complicated. They become much simpler if > instead of arithmetic the fundamental theory is a theory of finite > strings. As you already observed, arithmetic is easy to do with > finite strings. The opposite is possible but much more complicated. > The power operator can be built from repeated operations of the multiply operator. Will a terabyte be enough to store the Gödel numbers? -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer