Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: =?UTF-8?Q?Re=3A_G=C3=B6del=27s_actual_proof_and_deriving_all_of_the?= =?UTF-8?Q?_digits_of_the_actual_G=C3=B6del_numbers?= Date: Sat, 26 Oct 2024 08:57:58 -0500 Organization: A noiseless patient Spider Lines: 147 Message-ID: References: <87634d01e18903c744d109aaca3a20b9ce4278bb@i2pn2.org> <592109c757262c48aaca517a829ea1867913316b@i2pn2.org> <040cd8511c02a898516db227faa75dbc5f74a097@i2pn2.org> <17cad36a46956f00484737183121e8a2c9e742ef@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 26 Oct 2024 15:57:59 +0200 (CEST) Injection-Info: dont-email.me; posting-host="f00999e9e0e5447cf99e873d021c7ec9"; logging-data="3914594"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+cO6P/VQepAZw3PcK/5xDv" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ymEf5/UXf+BwodwrZOiGK9vzhPI= X-Antivirus: Norton (VPS 241026-2, 10/26/2024), Outbound message In-Reply-To: <17cad36a46956f00484737183121e8a2c9e742ef@i2pn2.org> Content-Language: en-US X-Antivirus-Status: Clean Bytes: 8656 On 10/25/2024 11:07 PM, Richard Damon wrote: > On 10/25/24 7:06 PM, olcott wrote: >> On 10/25/2024 5:17 PM, Richard Damon wrote: >>> On 10/25/24 5:52 PM, olcott wrote: >>>> On 10/25/2024 10:52 AM, Richard Damon wrote: >>>>> On 10/25/24 9:31 AM, olcott wrote: >>>>>> 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? >>>>>> >>>>> >>>>> Likely depends on how big of a system you are making F. >>>>> >>>> >>>> I am proposing actually doing Gödel's actual proof and >>>> deriving all of the digits of the actual Gödel numbers. >>>> >>> >>> Then try it and see. >>> >>> You do understand that the first step is to fully enumerate all the >>> axioms of the system, and any proofs used to generate the needed >>> properties of the mathematics that he uses. >>> >> >> Gödel seems to propose that his numbers are >> actual integers, are you saying otherwise? >> > > Not at all, just that they may be very large numbers. Are they less than one GB each? I want to see the c code that computes them. I want to know how many bytes of ASCII digits strings they are. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer