| Deutsch English Français Italiano |
|
<vfku48$78d0$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: news.eternal-september.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko <mikko.levanto@iki.fi> Newsgroups: comp.theory Subject: Re: Peano Axioms anchored in First Grade Arithmetic on ASCII Digit String pairs Date: Sun, 27 Oct 2024 10:37:28 +0200 Organization: - Lines: 120 Message-ID: <vfku48$78d0$1@dont-email.me> References: <ves6p1$2uoln$1@dont-email.me> <vetq7u$3b8r2$1@dont-email.me> <522ecce215e636ddb7c9a1f75bff1ba466604cc5@i2pn2.org> <veuvt9$3hnjq$1@dont-email.me> <87634d01e18903c744d109aaca3a20b9ce4278bb@i2pn2.org> <vev8gg$3me0u$1@dont-email.me> <eb38c4aff9c8bc250c49892461ac25bfccfe303f@i2pn2.org> <vf051u$3rr97$1@dont-email.me> <e3f28689429722f86224d0d736115e4d1895299b@i2pn2.org> <vf1hun$39e3$1@dont-email.me> <dedb2801cc230a4cf689802934c4b841ae1a29eb@i2pn2.org> <vf1stu$8h0v$1@dont-email.me> <592109c757262c48aaca517a829ea1867913316b@i2pn2.org> <vf37qt$fbb3$1@dont-email.me> <vf5430$sjvj$1@dont-email.me> <vf5mat$v6n5$4@dont-email.me> <vf7jbl$1cr7h$1@dont-email.me> <vf8b8p$1gkf5$3@dont-email.me> <vfa8iu$1ulea$1@dont-email.me> <vfassk$21k64$4@dont-email.me> <vfdjc7$2lcba$1@dont-email.me> <vfdlij$2ll17$1@dont-email.me> <vffj9k$33eod$1@dont-email.me> <vfg6j4$36im7$1@dont-email.me> <vfi7ng$3kub8$1@dont-email.me> <vfiq60$3ner2$3@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 27 Oct 2024 09:37:28 +0100 (CET) Injection-Info: dont-email.me; posting-host="9a2a304718252777197f6e54aa5a827a"; logging-data="237984"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19fOjrhHHD+TnKPT1AUMgNP" User-Agent: Unison/2.2 Cancel-Lock: sha1:TuZ1JYn6NYd1WEeGow2f77aHQcw= On 2024-10-26 13:17:52 +0000, olcott said: > On 10/26/2024 3:02 AM, Mikko wrote: >> On 2024-10-25 13:31:16 +0000, olcott said: >> >>> 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. >> >> It is possible but to say that x is the z'th power of y is overly >> complicated with a first order formula using just addition and >> multiplication. >> > > Just imagine c functions that have enough memory to compute > sums and products of ASCII strings of digits using the same > method that people do. Why just imagein? That is fairly easy to make. In some other lanugages (e.g. Python, Javascript) it is alread in the library or as a built-in feature. -- Mikko