What the theorems of Incompleteness or Undecidability assert...

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

Given that I see this is being misrepresented in prior conversations, I want to use this thread to help clarify the meaning of these theorems distinctly from other threads using assumptions about them for other justifications.

In particular, these theorem's were motivated by a question:

(1) Can we find some universal logic that can cover the full range of all specific logical systems?

AND/OR

(2) Are we permitted to use any logic, especially some possible universal one, with initial simple premises (including possibly none) to prove all of reality beyond mere abstraction, such as scientific truths?


Before moving on, I want to ask participants of this thread to tell me if they agree or disagree to this underlying motive before hand because if you disagree, we need to establish this by reference to those theorem's sources.

So do you agree these were the initial motivating questions?
If you don't, at least tell me if these are appropriate questions that you would think are reasonable to ask.
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Allow me to interject here.

Theorems, axioms, conjectures. All of these things exist in the realm of the conceptual and the abstract!

The assertions any such theorems would make are strictly about the structure and systemic properties of the logic-system itself.

None of the theorems ever tell us how the system would/will behave IF it is applied to real-world scenarios. You need empiricism for this!

And so the crux of the matter (as with all decisions) is human value.

What logic system do we want and why?
I want logical systems that work!

Towards WHAT end?

HOW do we distinguish between a logical system that works and a logical system that doesn’t work? What are our criteria for success and failure?

And I am going to openly state that I am a model-dependent realist.

All models with equivalent predictive utility are equivalently “real”.
Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

Logik,

I separated this discussion from your thread to attempt to figure out what the authors of the original theorems were about, not to something any of us interpret of them until we've established some common grounds. So we need to determine the motivating questions that first arose to do this. I need to determine ('decide'! :P ) whether you agree to those questions about motives first because I cannot prove nor disprove what you are thinking if we don't share the same initial understandings about those theorems, conjectures, etc.

So do you agree or disagree that those two questions were the original intent to digress into theorems about limitations of logic?
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

I agree with the way you have summarised the two positions BUT I think the strategy for enquiry is misguided and already pre-supposed too much.

Irrespective of the structural/systemic/provable/decidable properties of any logic system there is one decision that cannot be solved IN logic.

Given two logic systems ,A and B, which one is “better” and why?

The problem or choice plagues everything! Even choosing A logic. ANY logic!

Now, I do not know how to solve this problem except by saying “the one that works better”.

And we are immediately stuck asking “for what purpose?”

And we are also stuck with “define what works and doesn’t work means”.
Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

Logik wrote: Tue Feb 26, 2019 1:47 am I agree with the way you have summarised the two positions BUT I think the strategy for enquiry is misguided and already pre-supposed too much.

Irrespective of the structural/systemic/provable/decidable properties of any logic system there is one decision that cannot be solved IN logic.

Given two logic systems ,A and B, which one is “better” and why?

The problem or choice plagues everything! Even choosing A logic. ANY logic!
Okay, you appear to agree to the motivating questions.

But your assumption that we cannot decide between any SPECIFIC logic systems' capacity to work, is not what those theorems are about. That would be perfect suicide of the theorems themselves. If the logic of theorems about limitations are to be valid, AT LEAST the logic they are using to prove this HAS to be already deemed complete and consistent. It would fall in its own 'trap' without becoming contradictory.

The only prior limitation granted to ANY 'classic' logic system at all is that it cannot include Contradiction or it would have to be defined outside those theorems' range to discuss. They already know that 'paraconsistent' is not a term to define "logic" because those (the paraconsistent systems) are new systems (non-classical) that added this adjective to those systems that have more than mere binary truth values.

Non-classical ones ARE the modern versions that are used in things like Quantum Mechanics. such as Fuzzy Logic. The classic versions at their core require being defined as 'consistent' through the "Law of Identity", the "Law of Non-contradiction" and the "Law of Exclusive (Alternatives)". All these are actually one law expressed in different perspectives. So if you think that 'classical' logic has one but not the other, you are necessarily contradicting their intended meaning about what is 'classic'.
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Scott Mayers wrote: Tue Feb 26, 2019 2:18 am But your assumption that we cannot decide between any SPECIFIC logic systems' capacity to work, is not what those theorems are about. That would be perfect suicide of the theorems themselves.
I think there is more conceptual misunderstanding. A theorem. ANY theorem is a logical consequence of an axiom or axioms.

Because you are speaking of theorems, I am jumping to the conclusion that you already have SOME axioms which you accept as true.

Can you state them?

Like I said - computation is an empty canvas for evaluating consequences.

The consequences of WHAT? You decide.
Scott Mayers wrote: Tue Feb 26, 2019 2:18 am If the logic of theorems about limitations are to be valid, AT LEAST the logic they are using to prove this HAS to be already deemed complete and consistent. It would fall in its own 'trap' without becoming contradictory.
Another conceptual misalignment. What is your concept of a "proof" ? In any axiomatic system "proof" is something like "follows directly from the axioms, but if you are in an incomplete system there will be valid theorems which do not follow (Godel's work). So a much better definition of a "proof" (one that works across complete AND incomplete logical systems) is "proposition that does not contradict any of the axioms of the system".

Which leads right back to the previous paragraph: what are your axioms?

Another thing to note is that by Curry-Howard isomorphism we know EXACTLY what a "proof" is.
Any and all working programs are valid mathematical proofs.

What does Windows 10 prove? It proves that it's consistent with the axioms!
What are the axioms? Whatever YOU defined them as.

See the problem?

Logic is just LEGO. The STRUCTURE of logic (even if incredibly complex and internally consistent) needs NOT correspond to the STRUCTURE of reality in ANY way.

Scott Mayers wrote: Tue Feb 26, 2019 2:18 am The only prior limitation granted to ANY 'classic' logic system at all is that it cannot include Contradiction or it would have to be defined outside those theorems' range to discuss. They already know that 'paraconsistent' is not a term to define "logic" because those (the paraconsistent systems) are new systems (non-classical) that added this adjective to those systems that have more than mere binary truth values.
Turing-completeness guarantees no contradictions by the fact that computers manipulate information (e.g they manipulate matter!)
You cannot contradict information because you cannot contradict reality.

The laws of identity and non-contradiction are only necessary in a framework where it is POSSIBLE to produce contradictions.
I am still waiting for somebody to show me what a contradiction looks like in any programming language.
You can show me grammatical errors. You can show me syntax errors. You can show me semantic errors.
You can't show me a contradiction.

Scott Mayers wrote: Tue Feb 26, 2019 2:18 am Non-classical ones ARE the modern versions that are used in things like Quantum Mechanics. such as Fuzzy Logic. The classic versions at their core require being defined as 'consistent' through the "Law of Identity", the "Law of Non-contradiction" and the "Law of Exclusive (Alternatives)". All these are actually one law expressed in different perspectives. So if you think that 'classical' logic has one but not the other, you are necessarily contradicting their intended meaning about what is 'classic'.
I am contradicting the intended meaning of contradiction?

That's a little recursive e.g computational ;)
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Scott Mayers wrote: Tue Feb 26, 2019 12:17 am (2) Are we permitted to use any logic, especially some possible universal one, with initial simple premises (including possibly none) to prove all of reality beyond mere abstraction, such as scientific truths?[/b]
Having had a good night's rest I re-read this question and I want to point out its dualistic nature.

1. You are asking "Are we permitted?" Which (I will adhere to LEM for now so we don't get derailed) is the same as asking "Are we forbidden?"
Forbidden by whom and why?

2. You cannot prove ANYTHING about reality with logic. NOTHING. NADA. ZILCH. ZIP.
The concept of 'proof' is valid only within the context of logic, NOT in the context of using logic FOR THE PURPOSES OF reasoning about reality.

There is no guarantee for fitness of purpose anywhere on the box.

All you can prove with logic is that you have not violated the rules of the logic-system in any way. All that a proof tells you is that you haven't violated the grammar, semantics and vocabulary of the "language" that you are using.
All that a proof tells you is that you have made no DEDUCTIVE errors.

What a 'proof' cannot tell you is whether the STRUCTURE of your argument corresponds to the STRUCTURE of reality.

3. Taking the concept of being 'forbidden' - it is 'forbidden' to say 1 ∧ 1 = 0. WHY?

Because that is how ∧ is defined? WHY did you define ∧ that way?
WHY didn't you define ∧ so that 1 ∧ 1 = 0?

All that a mathematical/logical proof tells you is that you haven't broken any of the rules you PROMISED to adhere to.
Proof is accountability.

At this point your logic is still subject to "Garbage in - Garbage out".
Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

The 'classical' versus 'non-classical' definitions of logic is about 'consistency'. The classical ones are all consistency based whereas all the other variations accept some form of denial of 'consistency' as a requirement by their own extra additions of the classical versions.

All computers by default are 'classical' and thus, as you noted, cannot 'contradict'. So how or why you go against the very 'classical' forms begs why? The non-classical forms that allow contradiction are similar to the quantum computing. They may 'cheat' to create the illusion of contradicting or utilize newer design to approach this. Some believe it is possible via the weirdness of quantum entanglement. THAT is "non-classical"!

All computers and programs run through them are 'consistent' in that if the design is not malfunctioning, only the people are at fault (Gi/Go concept you embrace).

So this indicates you are misinformed about what 'classical' logic is.
------

I'll respond 'first-in, last-out' because you said you slept and redressed me with more clarity.
logic wrote: Scott Mayers wrote: ↑Mon Feb 25, 2019 5:17 pm
(2) Are we permitted to use any logic, especially some possible universal one, with initial simple premises (including possibly none) to prove all of reality beyond mere abstraction, such as scientific truths?[/b]
Having had a good night's rest I re-read this question and I want to point out its dualistic nature.

1. You are asking "Are we permitted?" Which (I will adhere to LEM for now so we don't get derailed) is the same as asking "Are we forbidden?"
Forbidden by whom and why?

2. You cannot prove ANYTHING about reality with logic. NOTHING. NADA. ZILCH. ZIP.
The concept of 'proof' is valid only within the context of logic, NOT in the context of using logic FOR THE PURPOSES OF reasoning about reality.
I assumed by "LEM" you are meaning "Law of Excluded Middle"? but can't see how this fits with the motive question(s)? [maybe this is "Lunar Excursion Module" for all I know?]

These are a response to the second motivating question which just adds to the first a question about whether we can extend logic beyond validity by beginning with apriori matters. I disagree with your answer but my opinion is distinct from the original motivating questions. This was a real question asked and a part of much of the controversies between scientific and logical/mathematical philosophy at the same time as the first question. "Permit" was about the fact that this is relatively 'political', not actually able to be deemed false. If laws of nature have no 'logic', you'd have to step back to question whether computers actually require being 'consistent'.

The point is that these questions historically gave rise to limitation-theorems in logic. Pioneers of the 19th century begun to realize paradoxes in logic, science, and reality in general, which was summed up by 1900 (for logic more specifically) as "Hilbert's Program". Basically, he listed a set of problems within mathematics (which was 'logic' limited to number and measure) that acted as a sort of manifesto to solve all of math in one unified umbrella. It was a hope to unify all laws of reality into a simple formulation based on a minimum set of common postulates, of which the fewest would ideally be zero or one. [Zero is preferable; but, just as HOW you responded above with absolution about logic to NEVER be able to prove anything about reality, this steps into politics because that kind of response is itself paradoxical and unable to be resolved without logic: what 'logic' can we allow/permit to use to 'disprove' that logic is itself not at the core of reality? There is none other than religious-type beliefs about limits based on emotion and our senses.]

Either way, paradoxes, which are real contradictions (until/unless resolved) are what the 'limits' pertain to.
logik wrote: There is no guarantee for fitness of purpose anywhere on the box.

All you can prove with logic is that you have not violated the rules of the logic-system in any way. All that a proof tells you is that you haven't violated the grammar, semantics and vocabulary of the "language" that you are using.
All that a proof tells you is that you have made no DEDUCTIVE errors.

What a 'proof' cannot tell you is whether the STRUCTURE of your argument corresponds to the STRUCTURE of reality.
And this is precisely proof of your own that the questions of the past were worthy of challenging. If there is a 'universal' logic, then all things could be unified to one standard of proof. This would require a base-logic or 'first-order' one of which all other different types can resort to as a foundation.

A 'proof' only deals with structure, not the 'truth' of the premises but the theorems that are validated of them require the very first inputs to be gambled as true. If the domain of the first input premises being used are true though, formal logic (deductive) requires the conclusion to follow or, regardless of the 'reality' of the claims of the inputs, those conclusions about reality are also invalid. So logic IS necessary for proofs about reality except for the core 'observations' that cannot be questioned by anyone other than the subjective individuals senses. Anything else beyond that is 'politics'. Science, for instance, is a 'politic' in that it requires AGREEMENT of subjective observers who vote on which definitions, interpretations, and logic systems that are 'permitted' to be used in the study of reality.
3. Taking the concept of being 'forbidden' - it is 'forbidden' to say 1 ∧ 1 = 0. WHY?
Now you are 'transferring' definitions in your head to 'forbidden' when you link it to 'permitted' (the actual word I used). What is 'permitted' about my statement on motives was to the political option to allow some particular system of reasoning (logic) to be used within a field, like science. What is 'permitted' deals with whether upon arguing between people if we must accept that logic is 'allowed' to prove or disprove something about reality, ....not about whether nature 'permits' variable logic systems to be used in principle.

You are jumping over the motivational problem here. The motivation of the limit theorems were about whether a universal system of logic as a 'parent' logic....a metalogical system....could be found that all other complex ones could be rooted in. It doesn't concern itself with whether one can create different architectures or programs that are 'free' to define its terms distinctly.
logik wrote: All that a mathematical/logical proof tells you is that you haven't broken any of the rules you PROMISED to adhere to.
Proof is accountability.

At this point your logic is still subject to "Garbage in - Garbage out".
We are not on the same page. The "garbage in- garbage out" issue relates but logic calls this 'validity'. The logic is only as "sound" (meaning maps to reality) if it is BOTH valid and its content 'true' to reality.

[I just wiped out a block of response and am not rewriting. They could use a 'select-all' option here. I tried to highlight the whole thing to 'save' and it instead deleted the end material!]

I'll have to try again later. For now I'll post and you're welcome to respond at least to this.
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm The 'classical' versus 'non-classical' definitions of logic is about 'consistency'. The classical ones are all consistency based whereas all the other variations accept some form of denial of 'consistency' as a requirement by their own extra additions of the classical versions.
This is the roseA = roseB problem. What is the difference between a consistent and an inconsistent system?

What is your paragon for 'consistency'?
By the Curry-Howard isomorphism mine is Turing-completeness.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm All computers by default are 'classical' and thus, as you noted, cannot 'contradict'.
Correlation is not causation. They cannot contradict BECAUSE when you implement the mathematics of a Boolean gate in a transistor it is IMPOSSIBLE for a bit to be low AND high voltage at the same time. If that were to happen it's either a hardware problem or your 'classical' machine just went Quantum...
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm So how or why you go against the very 'classical' forms begs why?
a
Because it is undecidable. Consistent-but-undecidable is not Turing-complete and if it's not Turing-complete it is not representative of MY mind.
Because I make choices when I think. I recall memories. I store memories for later retrieval.

I think factually and counter-factually. The process most definitely does NOT fit in the structures of classical logic.

I don't like prison cells for my mind.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm The non-classical forms that allow contradiction are similar to the quantum computing. They may 'cheat' to create the illusion of contradicting or utilize newer design to approach this. Some believe it is possible via the weirdness of quantum entanglement. THAT is "non-classical"!
Here is a paraconsistent logic which violates identity while preserving LEM and LNC.

https://repl.it/repls/StrangeLiquidPolyhedron
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm All computers and programs run through them are 'consistent' in that if the design is not malfunctioning, only the people are at fault (Gi/Go concept you embrace).
OK great! We are on the same page. If you accept the Curry-Howard isomorphism then working computer programs are proofs.
And so if you are calling a non-malfunctioning program 'consistent' this is synonymous meaning with 'valid'.
Proofs compute. A Program without errors is DEDUCTIVELY valid and contains no grammatical/semantic errors.

That is ALL validity buys you. Guarantee that you haven't made a LINGUISTIC error. You have good grammar! **pats back**

It makes absolutely no guarantees whether your system produces anything of value whatsoever.
It definitely does not give you "correspondence".

Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm So this indicates you are misinformed about what 'classical' logic is.
It is complete-but-undecidable and therefore NOT Turing-complete.
Its grammar and semantics do not allow for expressing things like storing/recollecting memories OR if-then-else type expressions and therefore it is not representative of the way I think.

What am I misinformed about?
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm I assumed by "LEM" you are meaning "Law of Excluded Middle"? but can't see how this fits with the motive question(s)?
These are a response to the second motivating question which just adds to the first a question about whether we can extend logic beyond validity by beginning with apriori matters. I disagree with your answer but my opinion is distinct from the original motivating questions. This was a real question asked and a part of much of the controversies between scientific and logical/mathematical philosophy at the same time as the first question. "Permit" was about the fact that this is relatively 'political', not actually able to be deemed false. If laws of nature have no 'logic', you'd have to step back to question whether computers actually require being 'consistent'.
Lets take a step back here though. By Curry-Howard EVERY SINGLE WORKING PROGRAM is valid AND complete.

Code: Select all

X = 5
This is a valid/complete logical system.

All 15 million lines of the Linux kernel. Valid and Complete logical system.

Neither my 1-liner above nor the linux kernel are exactly representative of anything pertaining to reality (I think)?
So it seems to me that consistency (validity?) is necessary-but-insufficient.

A logical system's STRUCTIRE being internally consistent does not (in any way) suggest that the system's structure corresponds to the structure of reality in any useful or meaningful way.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm The point is that these questions historically gave rise to limitation-theorems in logic. Pioneers of the 19th century begun to realize paradoxes in logic, science, and reality in general, which was summed up by 1900 (for logic more specifically) as "Hilbert's Program". Basically, he listed a set of problems within mathematics (which was 'logic' limited to number and measure) that acted as a sort of manifesto to solve all of math in one unified umbrella. It was a hope to unify all laws of reality into a simple formulation based on a minimum set of common postulates, of which the fewest would ideally be zero or one. [Zero is preferable; but, just as HOW you responded above with absolution about logic to NEVER be able to prove anything about reality, this steps into politics because that kind of response is itself paradoxical and unable to be resolved without logic: what 'logic' can we allow/permit to use to 'disprove' that logic is itself not at the core of reality? There is none other than religious-type beliefs about limits based on emotion and our senses.]

Either way, paradoxes, which are real contradictions (until/unless resolved) are what the 'limits' pertain to.
The most interesting of Hilbert's problems (as far as I can tell) is his Entscheidungsproblem.

Which is exactly the roseA = roseB problem :)
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm And this is precisely proof of your own that the questions of the past were worthy of challenging. If there is a 'universal' logic, then all things could be unified to one standard of proof. This would require a base-logic or 'first-order' one of which all other different types can resort to as a foundation.
Your use of 'proof' is ambiguous here. Curry-Howard (computaqbility) is an objective and universal standard (PROOF OF) validity.
If standardization you want - that is solved.

This is precisely WHY I insisted on tackling the is logic A better than logic B problem? Define "better" ;)
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm A 'proof' only deals with structure, not the 'truth' of the premises but the theorems that are validated of them require the very first inputs to be gambled as true. If the domain of the first input premises being used are true though, formal logic (deductive) requires the conclusion to follow or, regardless of the 'reality' of the claims of the inputs, those conclusions about reality are also invalid. So logic IS necessary for proofs about reality except for the core 'observations' that cannot be questioned by anyone other than the subjective individuals senses. Anything else beyond that is 'politics'. Science, for instance, is a 'politic' in that it requires AGREEMENT of subjective observers who vote on which definitions, interpretations, and logic systems that are 'permitted' to be used in the study of reality.
Does not not bother you though that all Mathematical logic is deductive in an inductive reality?
It sure strikes me as using the wrong tool for the job...

Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm Now you are 'transferring' definitions in your head to 'forbidden' when you link it to 'permitted' (the actual word I used). What is 'permitted' about my statement on motives was to the political option to allow some particular system of reasoning (logic) to be used within a field, like science.
Permit/forbid.
Allow/deny.

Potato - potato.

Science is a pragmatic institution, not a prescriptive one.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm What is 'permitted' deals with whether upon arguing between people if we must accept that logic is 'allowed' to prove or disprove something about reality, ....not about whether nature 'permits' variable logic systems to be used in principle.
That's an easy answer. No.

Logic computes consequences. With a certain margin of error.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm You are jumping over the motivational problem here. The motivation of the limit theorems were about whether a universal system of logic as a 'parent' logic....a metalogical system....could be found that all other complex ones could be rooted in.
The answer is yes. The Type 0 Chomsky grammar is the super-set of all regular grammars.

https://en.wikipedia.org/wiki/Chomsky_hierarchy
https://en.wikipedia.org/wiki/Regular_language
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm It doesn't concern itself with whether one can create different architectures or programs that are 'free' to define its terms distinctly.
Unfortunately this paragraph is contradictory with the one before.
Type 0 Chomsky grammars are Turing complete and therefore isomorphic to Lambda calculus.
And so you have infinite freedom to define any and all of your terms.

Of course, this is a very intuitive conclusion.
Logic is just language and so without some form of limits (STRUCTURE) anything goes.
Where do you get STRUCTURE from? Your mind - of course. You DESCRIBE the structure of your experiences.

More limits arrive when you marry the software with physical reality: hardware.
Then things like time, energy, space (memory) become things to be taken into account.
Scott Mayers wrote: Tue Feb 26, 2019 8:17 pm We are not on the same page. The "garbage in- garbage out" issue relates but logic calls this 'validity'. The logic is only as "sound" (meaning maps to reality) if it is BOTH valid and its content 'true' to reality.
I thought we agreed that validity/consistency was the same as 'working software'?


https://en.wikipedia.org/wiki/Decidability_(logic)
Each logical system comes with both a syntactic component, which among other things determines the notion of provability, and a semantic component, which determines the notion of logical validity.
If validity is strictly a semantic notion (leaning towards Tarski's work) and all meaning is subjective then logical semantics cannot originate anywhere else but with the person CONSTRUCTING the logic.

Of course - this is to be expected because logic is just a Metalanguage all language ever was (is?) is a tool for self-expression.

That we are trying to model reality IN language, well... Reality doesn't care what we want.
And so all you can ever define IN language is your metaphysical experiences OF reality. NOT reality itself.

Still! Computer are useful for other things than 'defining reality'....
Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

logik wrote:
Scott Mayers wrote: ↑Tue Feb 26, 2019 1:17 pm
So this indicates you are misinformed about what 'classical' logic is.
It is complete-but-undecidable and therefore NOT Turing-complete.
Its grammar and semantics do not allow for expressing things like storing/recollecting memories OR if-then-else type expressions and therefore it is not representative of the way I think.

What am I misinformed about?
"Turing-complete" describes the universal Turing machines' capacity to solve all problem's ideally if given an infinite amount of time. This is what Turing designed as a complete particular system used to ask whether he could device a program that can 'finitely' decide if all Turing machines (ie, programs) cover all possible computational (logical) problems.

So he devised a universal Turing machine (a general computer) that was itself 'complete' in principle, then showed that for the list of all possible numbers that represent the code for each program (particular Turing machine), you should be able to pick one of those programs programmed to solve at least ONE problem of the infinite it is expected to solve.

So pick, say, writing a program that attempts to decide whether the list of numbers representing all possible programs run by the universal machine can finitely determine (decide) which ones will halt or not. Such a program cannot halt itself for ANY finite list of programs. If it cannot determine this itself without running infinitely, it cannot 'decide' with closure (completeness) that even a universally designed Turing machine can solve all problems, .....thus computation (as the process of logic) is incomplete.

"Classical" logic(s) are 'complete' on their own domain. They can also 'decide' all problems within their domains or they would not be called 'complete'. The Entscheidungsproblem (I hate using foreign languages that hide its meaning) is that 'halting' sub-program (algorithm) used IN that universal Turing machine to test whether it CAN completely ask all possible programs (including itself) when represented as data, to solve a finite question (can this given program 'halt'). Because that finite question itself was about asking an infinity of possible machines that can possibly be created, for any 'finite' list of possible programs that are complete, it cannot cover all possible programs finitely for that very program to tell us a clear yes or no. Thus that proved that ONE such program, the halting program in particular, cannot do what it was programmed to do: finitely answer something about something infinite.
Logik wrote:
Scott Mayers wrote: ↑Tue Feb 26, 2019 1:17 pm
The 'classical' versus 'non-classical' definitions of logic is about 'consistency'. The classical ones are all consistency based whereas all the other variations accept some form of denial of 'consistency' as a requirement by their own extra additions of the classical versions.
This is the roseA = roseB problem. What is the difference between a consistent and an inconsistent system?
A 'consistent' system is one in which the axioms of the logical system being used, themselves do not contradict each other. "Completeness" is about whether all possible inputs to the whole system those logical axioms allow can have a definite conclusion (ie. a decidable outcome). Your picture matching example is not about 'decisions' when you stick to ONE of those hypotheses that defined 'true' from 'false'. That system would be INCONSISTENT if you kept both hypotheses as axiomatic choices.

You cannot define a system that has both,
X == X and X != X [or X = X and X = not-X] IF you define a system as requiring 'consistency'.

A paraconsistent logic might be one that is 'consistent' to defining some law as
IF (X ==not-X) then DO Y

It happens to BE 'constructive', by the way, because such a rule would act to force a re-consistency by splitting the possibilities into parallel ways or places.
IF (X == not-X) then (Y[1] = X) and (Y[2] = not-X) where Y[1] is parallel but exclusive to Y[2].
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Scott Mayers wrote: Tue Feb 26, 2019 11:42 pm "Turing-complete" describes the universal Turing machines' capacity to solve all problem's ideally if given an infinite amount of time. This is what Turing designed as a complete particular system used to ask whether he could device a program that can 'finitely' decide if all Turing machines (ie, programs) cover all possible computational (logical) problems.

So he devised a universal Turing machine (a general computer) that was itself 'complete' in principle, then showed that for the list of all possible numbers that represent the code for each program (particular Turing machine), you should be able to pick one of those programs programmed to solve at least ONE problem of the infinite it is expected to solve.

So pick, say, writing a program that attempts to decide whether the list of numbers representing all possible programs run by the universal machine can finitely determine (decide) which ones will halt or not. Such a program cannot halt itself for ANY finite list of programs. If it cannot determine this itself without running infinitely, it cannot 'decide' with closure (completeness) that even a universally designed Turing machine can solve all problems, .....thus computation (as the process of logic) is incomplete.

"Classical" logic(s) are 'complete' on their own domain. They can also 'decide' all problems within their domains or they would not be called 'complete'. The Entscheidungsproblem (I hate using foreign languages that hide its meaning) is that 'halting' sub-program (algorithm) used IN that universal Turing machine to test whether it CAN completely ask all possible programs (including itself) when represented as data, to solve a finite question (can this given program 'halt'). Because that finite question itself was about asking an infinity of possible machines that can possibly be created, for any 'finite' list of possible programs that are complete, it cannot cover all possible programs finitely for that very program to tell us a clear yes or no. Thus that proved that ONE such program, the halting program in particular, cannot do what it was programmed to do: finitely answer something about something infinite.
OK but the Turing machine is only infinite in theory. In practice - physics.
And so we have a bloody useful tool for determine which yes/no questions we CAN attempt to answer in a <reasonable amount of time>.

This is what computational complexity is all about.

That is PRECISELY why I posed the roseA = roseB problem in that way.

The problem is decidable IF you know how.
Scott Mayers wrote: Tue Feb 26, 2019 11:42 pm A 'consistent' system is one in which the axioms of the logical system being used, themselves do not contradict each other.
Agreed. This is why Curry-Howard gets us to the mark. If the axioms were inconsistent - the compiler/interpreter would throw an error.
Scott Mayers wrote: Tue Feb 26, 2019 11:42 pm "Completeness" is about whether all possible inputs to the whole system those logical axioms allow can have a definite conclusion (ie. a decidable outcome). Your picture matching example is not about 'decisions' when you stick to ONE of those hypotheses that defined 'true' from 'false'. That system would be INCONSISTENT if you kept both hypotheses as axiomatic choices.
Of all the logical properties, completeness is the one I care about the least. Human knowledge IS incomplete. Human knowledge can NEVER be complete.

Scientific theories are model-approximations. OBVIOUSLY we will leave out details.
We are looking at the world top-down. There is A LOT of information. To even begin to describe reality in its completeness requires A LOT of bandwidth (to retrieve the information FROM reality and INTO our heads).

Methinks some pragmatic consideration and compromises are necessary here :)
Scott Mayers wrote: Tue Feb 26, 2019 11:42 pm You cannot define a system that has both,
X == X and X != X [or X = X and X = not-X] IF you define a system as requiring 'consistency'.
But you CAN DEFINE it (as you have done above) AND you can realize it with logic gates. I don't know why you would want to do such a thing since it always produces 0...
User avatar
Arising_uk
Posts: 12314
Joined: Wed Oct 17, 2007 2:31 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Arising_uk »

Logik wrote:... Its grammar and semantics do not allow for expressing things like ... if-then-else type expressions and therefore it is not representative of the way I think. ...
(P → Q) & (~P → R)?
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Arising_uk wrote: Wed Feb 27, 2019 12:32 am
Logik wrote:... Its grammar and semantics do not allow for expressing things like ... if-then-else type expressions and therefore it is not representative of the way I think. ...
(P → Q) & (~P → R)?
Is there even a boolean operator for this?

Let me see how the truth table plays out.
Logik
Posts: 4041
Joined: Tue Dec 04, 2018 12:48 pm

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Logik »

Arising_uk wrote: Wed Feb 27, 2019 12:32 am
Logik wrote:... Its grammar and semantics do not allow for expressing things like ... if-then-else type expressions and therefore it is not representative of the way I think. ...
(P → Q) & (~P → R)?
So the booelean formula of the above is ( not p and q ) and ( p and r ) and the truth table is this

https://repl.it/repls/InsubstantialWelllitCommunication

Code: Select all

False False False => False
False False True => False
False True False => False
False True True => False
True False False => False
True False True => False
True True False => False
True True True => False
This is a rather inefficient way to remain indecisive ;)

But take note. While you will probably find some permutation to generate a truth-table that corresponds to your expectations, notice how unnatural it is to think this way!
Last edited by Logik on Wed Feb 27, 2019 11:26 am, edited 1 time in total.
Scott Mayers
Posts: 2446
Joined: Wed Jul 08, 2015 1:53 am

Re: What the theorems of Incompleteness or Undecidability assert...

Post by Scott Mayers »

logik wrote:
Scott Mayers wrote: ↑Tue Feb 26, 2019 4:42 pm
You cannot define a system that has both,
X == X and X != X [or X = X and X = not-X] IF you define a system as requiring 'consistency'.
But you CAN DEFINE it (as you have done above) AND you can realize it in the way that I showed you how. By gaming the sampling interval.

You see X == X and X != X. I see:
X == X: store 1 in register A
X != X: store 0 in register B
A and B: 0

The LNC contradicts itself out of existence when you implement it on a computer.
I have to say I like your background even if we might not be precisely in agreement.

This actually proves something about reality itself and similar to what I used to demonstrate HOW you can begin with absolutely nothing in totality to derive something. That is, you think that the computer program is presenting a contradiction when it is actually the underlying logic of reality itself (as a whole).

0 == (0 and 1)

but

1 != (0 and 1)

...which implies that 1 can only equal itself.... an Identity.

The computer operates this way because WE are the ones who have to turn it on for it to run. The '1' is represented as a charge or current of electrons (posited) in the system from an initial non-charged, non-current system [relatively to our construction of it of course.]

Assigning 0 to (A == A) is equivalent to assigning 0 == 1 in a way that one might say, "From nothing, we can get something."

We need to take a step back for clarity on the machine level of a computer though.

A 'variable' is a memory space. If that memory 'space' is constant, it is hardwired as 1 = passing current at some point, or 0 = no current (or no actual hardwired connection).

The memory address though is also represented by a number. So we can think of the literal memory space as a box labeled either 0 (for empty) or 1 (for not-empty). The contents of it in fact do not have to fit with the box's label. So we can have 0 or 1 in side either box.

The distinction is about the hardware, which represents connections/current or lack of it . You can have an address defaulted to a hardwired original place and thus call it address 0. Any other address is 1 or greater. For simplicity, we can assume only two addresses. The contents are 'variable' (can be 0 xor 1) [or (0 or 1) if we allow for degrees of charge]

Assigning the variable in a program to seek the memory space labeled '0' with a '0' is (0 = 0) in computing. This is not 'logical equality'. However if we assign memory space labeled '1' with a '0', we can check for equality via the "==" but now have to clearly specify the distinction THAT both sides of that symbol are comparing the two memory spaces' contents, not their labels, such as, perhaps, ('0' == '1'). Going back, the actual (0 = 0) should be rendered as ('0' = 0) and the other memory unit as ('1' = 0). This clearly points out the problem you may be thinking. Note that we can also assign the contents of memory of one to the contents of the memory of the other. This too is distinct. To assign whatever is in variable '1' to variable '0', we need to do operations using AND and/or OR procedures. This can only be summarized in a higher-order language by something like ('0' = '1') but means, assign the contents of '1' to the contents of '0'.



Here is how I use it regarding Absolutely Nothing (capitalized given it would be the unique state, not a point of many in space). Let Totality be the label for totality and we assign its value as a 'something' == 1. At this extreme, the container, Totality is a something that is Absolutely One Thing in meaning to which nothing nor anything is outside of it. So this is not 'assigned' 1 but literally describes the container. (a container that contains a reference to itself such as, using the example above,

'1' = '1'

which is an infinite loop. It tries to assign the content of that which is called '1' into itself reflectively.

So NOW, given absolutes, you CAN assign the state of being ('1' == '1') to the variable '0' (standing for Absolutely nothing.

'0' = ('1'== '1').

If this whole statement is 'true', '0' is one real thing and so contradicts being a nothing.
If 'false', the meaning of Totality would have to be denied true (or existent).

Thus we have a 'contradiction' right? BUT wait! If Totality were an absolute nothing, it would not even hold meaning to neither what is or is not 'true' nor requires BEING 'consistent'. There is no law there that restricts it being so.

On the other hand, the case is still contradictory if we treat Totality as 'true' but is forced to be some concept apart from itself. Thus there are at least two factors if Totality were to be 'true': One for it being 'true' at least, and one for the meaning of 'truth'.

Totality thus CAN be an original Absolutely Nothing but Absolutely Nothing can come about if or once at least one thing is 'true'.

Follow me on this?
Post Reply