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: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon 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: Thu, 31 Oct 2024 19:08:55 -0400 Organization: i2pn2 (i2pn.org) Message-ID: References: <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: Thu, 31 Oct 2024 23:08:55 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="366200"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US In-Reply-To: X-Spam-Checker-Version: SpamAssassin 4.0.0 Bytes: 15535 Lines: 296 On 10/31/24 8:15 AM, olcott wrote: > On 10/31/2024 4:45 AM, Mikko wrote: >> On 2024-10-30 12:13:43 +0000, olcott said: >> >>> On 10/30/2024 4:57 AM, Mikko wrote: >>>> On 2024-10-29 13:25:34 +0000, olcott said: >>>> >>>>> On 10/29/2024 2:38 AM, Mikko wrote: >>>>>> On 2024-10-28 14:04:24 +0000, olcott said: >>>>>> >>>>>>> On 10/28/2024 3:35 AM, Mikko wrote: >>>>>>>> On 2024-10-27 14:29:22 +0000, olcott said: >>>>>>>> >>>>>>>>> On 10/27/2024 4:02 AM, Mikko wrote: >>>>>>>>>> On 2024-10-26 13:57:58 +0000, olcott said: >>>>>>>>>> >>>>>>>>>>> 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? >>>>>>>>>>>>>>>>> ========== REMAINDER OF ARTICLE TRUNCATED ==========