But probably only because it is NP-complete.

I'm not sure it is. Consider zip bombs, which were a way to overwhelm PCs and make them crash or ton overwhelm anti-virus software. The zip bomb is just a highly compressible file, something like a a text block of nothing but a the same few letters repeated a tremendous number of times. This is extremely compressible because it can be summarized as something like "print XYZ 10¹⁰⁰ times."

What makes the Hamiltonian Path problem intractable is precisely the extremely large number of operations and this can be true for any program provided it has enough steps.

E.g.:

One example of a zip bomb is the file 42.zip, which is a zip file consisting of 42 kilobytes of compressed data, containing five layers of nested zip files in sets of 16, each bottom-layer archive containing a 4.3-gigabyte (4294967295 bytes; 4 GiB − 1 B) file for a total of 4.5 petabytes (4503599626321920 bytes; 4 PiB − 1 MiB) of uncompressed data.

Excel used to be terrible at this sort of thing in terms of using up a ton of resources to try to visually represent (relatively) small amounts of data.

The other interesting question is how to account for forms of non-temporal knowledge

Not sure what you have in mind here. Non-temporal knowledge makes me think of God's self knowledge in Plotinus or something like that.

This user has been deleted and all their posts removed.

This user has been deleted and all their posts removed.

Since one entails the other but other does not entail one, we may say that everytime «A implies a contradiction» is false, «A does not imply a contradiction» is true; but it is not everytime «A does not imply a contradiction» is true that «A implies a contradiction» will be false. Therefore there is an assymetrical relationship between the two statements quoted.
The prover confirms my intuition:
(a→¬(b∧¬b)) does not entail ¬(a→(b∧¬b))
¬(a→(b∧¬b)) entails (a→¬(b∧¬b)) — Lionino

Which one of the above phrases are you saying is the english translation of (a→¬(b∧¬b))?

It's either «A implies a contradiction» is false
or «A does not imply a contradiction» is true, right?

But consider this:
((a → ¬(b∧¬b)) ∧ ¬a) → (a → (b∧¬b)) is valid

(a→¬(b∧¬b)) doesn't actually stop a from implying a contradiction - it can be assumed true, and still be the case that a implies a contradiction.

¬(b∧¬b) just means (b v ¬b)

This user has been deleted and all their posts removed.

https://www.umsu.de/trees/#~3a~5(a~5~3(b~1~3b))


https://www.umsu.de/trees/#~3a~5(a~5(b~1~3b))

I would reword it from "a does not imply a contradiction" to "a implies this particular non-contradiction".

And when a is false, it implies everything, contradictions and non contradictions.

This user has been deleted and all their posts removed.

This user has been deleted and all their posts removed.

This user has been deleted and all their posts removed.

the goal anyway is to translate "A does not imply a contradiction", not any other phrase. — Lionino

This might seem crazy to you, but I would translate that as just A, or in other words, A is true. If you are stating, for a fact, in classical logic, A definitely doesn't imply any contradictions, and we also know that false statements necessarily do imply contradictions, then the only way to say "A definitely implies no contradiction" is to say "A is true"

Depending on circumstances, it might make more sense to say something like "A can't be proven to imply a contradiction" rather than "A doesn't imply a contradiction". Classic symbolic logic is very constraining, and it's hard to express certain things that seem simple in natural language.

This user has been deleted and all their posts removed.

Elvis is a man does not imply that Elvis is both mortal and immortal – (A → ¬(B and ¬B)) — Lionino

Is that the right English translation of that?

Keep in mind that ¬(B and ¬B) is equivalent to B or ¬B - would you say A → (B or ¬B) can be worded as "Elvis is a man does not imply that Elvis is both mortal and immortal"?

This user has been deleted and all their posts removed.

This user has been deleted and all their posts removed.

I think it should be worded as "Elvis is a man DOES imply that elvis is NOT simultaneously immortal and mortal".

It positively implies something, rather than "does not" imply something.

Thinking of the two as timelessly equivalent leads to the Scandal of Deduction. P(I) should allow us to know O in "no time at all," on the view that they are the same exact thing. In reality, no computation occurs in "no time at all."

Consider a second program Q that simply takes the output of P as its input and prints it to tell a user what the shortest path is.

Well, if we have Q(P(I)) it is clear that Q cannot print until P is finished computing. But if the output of Q is equivalent with Q, this is a strange thing indeed.

A helpful way to think about this is by looking at the way physical computation always involves communication and the ways in which it can be explained/moddled in terms of communication theories: https://link.springer.com/article/10.1023/B:MIND.0000005133.87521.5c

Likewise, 2+2=4 can't be the same thing as 2+2 is 4 in terms of computation for other reasons. There are an infinite number of programs with 4 as their output (given some input). But (6+2)/4 is not the same computation as 2+2. If programs just are their outputs then all sorts of completely different programs, some very quick to execute, other intractable, all end up being the same thing. But then why are some intractable, taking millions of years, and some take a millisecond if they are identical? Clearly they aren't identical in every way.

Hence why I said, "in some sense it might make sense to think of 2+2 is 4." However, this assumption seems flawed when one discussed computation in general and physical computation in particular.

But the "Scandal of Deduction," is about why we find the results of deduction and computation surprising and informative. We are physical beings. We do not compute in "no time at all."

This user has been deleted and all their posts removed.

This user has been deleted and all their posts removed.

That much I can agree with under a formalist/nominalist view of mathematics. If we take that mathematical objects are platonic objects, where, by definition, the two would be timelessly equivalent, does the Scandal of Deduction make mathematical platonism troublesome?

I don't think so. However numbers exist, they don't seem exist in the way physical systems do, so this is not strictly an issue.

It is however relevant for how the assumptions of platonism affect how we think of physics. Folks like Gisin have argued, somewhat convincingly I think, that assumptions about math have been key to how physicists think of physics. In particular, these assumptions are used to support claims about eternalism or "the block universe" (as opposed to local becoming, the growing block universe, etc.). His argument is that intuitionist assumptions make a better grounding for physics.

I also think these issues could be used as an argument against platonism, something to the effect of: "the way number is actually instantiated differs radically from the assumptions of platonism." However the two aren't necessarily in conflict.

If you think the above is an exemplification of the rebuttal, do you think it is a valid argument? The only way I see is by denying β which is denying the laws of chemistry, which is back to the problem of induction (how do you know every DNA degenerates?)

I don't think it gets around the problem of the premises having to include the conclusion. The conclusion still always follows with p=1 and must in a way be "contained" in what one starts with.

That quote also seems to assume some potentially problematic things about what constitutes a "natural law," but that's sort of aside the point.

Is this about all computation then and what I wrote above irrelevant?

It perhaps depends on how much you embrace pancomputationalism in physics and information theoretic explanations of the other special sciences. If we think number only appears in nature in terms of computation and process then that seems suggestive at the very least. But I don't think process metaphysics ultimately rules out more platonesque views like Hegel's doctrine of concept and essence, or the Patristics differentiation between logoi and Logos.

The entirety of this debate revolves around a vague OP:

Do (A implies B) and (A implies notB) contradict each other?

If you are asking:

"Is 'A -> B && A -> !B' a contradiction (i.e., itself contradictory)?"

Then the answer is clearly no. If you are asking:

"Is 'A && A -> B && A -> !B' a contradiction (i.e., itself contradictory)?"

Then the answer is clearly yes.

Everyone is just interpreting the OP's question, because it is too vague, one way or the other.

The way I've stated it is relevant to this:

https://en.wikipedia.org/wiki/Barbershop_paradox

The way I stated it was no more or less vague than it needed to be for it's relationship to that.

What makes the Hamiltonian Path problem intractable is precisely the extremely large number of operations and this can be true for any program provided it has enough steps. — Count Timothy von Icarus

An NP-Complete problem is, among other things, one that has no known polynomial time algorithm/solution. The point being that your P(I) = O is an approximate solution, not a deterministic solution. If O is only an approximation of a solution then of course it deviates from the ideal solution, and from an isomorphic relation.

They are found in "S". Or you can just replace "S" with axioms of the theory. Axioms are naturally assumed.

...

I don't. I know that S and ¬P can't coexist. I know that S, so ¬P can't be the case. ¬¬P is P. — Lionino

See:

<Lionino's "reductio" seems to be ambiguous between senses (2) and (3)> — Leontiskos

So:

(S∧¬P)→(B∧¬B)
S
∴ P — Lionino

What is happening is apparently:

1. (P∧Q)→R
2. ¬R
3. ∴ ¬(P∧Q)

As noted earlier in the thread, a reductio is not representable in the object language, and therefore what you present is not a reductio in any formal sense.

The first thing to note is that the conclusion is ¬(P∧Q). In the first place P and Q can both be false. But if we add an additional condition that they cannot both be false, ¬(¬P∧¬Q), then to stipulate that one is true or false automatically determines the other value, and yet there is no principled reason to stipulate such a thing apart from mere stipulation. Or, if we stipulate that one is true, as you did, then we must accept that the other is false, even without the additional condition. Still, we have no reason to stipulate P instead of Q. There is no theory here or set of axioms, except in a purely stipulative and imaginary way. P and Q are exactly on a par as far as the formalization goes.

1. (P∧Q)→R
2. ¬R
3. ∴ ¬(P∧Q)
4. __Suppose P
5. __∴ ¬Q

From the supposition we learn (P→¬Q), at which point P must be further asserted beyond supposition if we are to actually arrive at ¬Q:

• (P→¬Q)
• P
• ∴ ¬Q

(To suppose P and to assert P are here two different things)

..But it always goes back to the question of why we preferred P in (4) rather than Q.

Note too how this is different from a reductio:

(S∧¬P)→(B∧¬B)
S
∴ P — Lionino

...insofar as your supposition produces no contradiction at all, and the thing you suppose is never rejected. This sort of underlines that you are merely supposing that something is true without any reason. This is what confused me in my initial reply. When you called your proof a reductio I assumed your supposition was being rejected.

The phrase «A does not imply a contradiction» really means specifically «A being true, it does not imply a contradiction». I think this meaning is indeed encapsulated in A→¬(B∧¬B), especially when it can be translated as «A implies True». — Lionino

I don't see it this way. I think the phrase, "A does not imply a contradiction," either means, "A implies something and that something is not a contradiction," or else, "Whatever is implied by A, it is not a contradiction." Both of these are examples of meta-language, and neither is represented by A→¬(B∧¬B). The first means, "A implies B and B is not ¬A." The second means that whether or not A implies anything, it does not imply ¬A.

In any case we have to distinguish these two propositions:

• A→(B∧¬B)
• A→¬A

Then why not reference that in the OP? Otherwise, it is simply too vague.

Allen never leaves the shop without Brown (¬A ⇒ ¬B)

This is a poorly translated sentence into logic: the fact that allen never leaves the shop without brown does not imply that brown cannot be in the shop when allen is not there. On the contrary, it just means that when allen was present in the shop and then left (or brown was in the shop when allen was there), one can be sure that brown (or allen) left with him; which can't be expressed accurately without temporal logic. E.g., just because you know that "when my niece is with me in walmart, she will not leave the store without me", it does not follow that "when I am in Walmart, my niece is with me"...that's just bad logic. Even when considering the other axiom (that at least one is there) it does not follow that ¬A ⇒ ¬B from the sentential form of the axiom.

If I grant the logical form which they are translating to (such that is the axiom is actually '¬A ⇒ ¬B'), then it still the case, as I mentioned before, that there is no paradox at all: 'A ⇒ ¬B' and '¬A ⇒ ¬B' are not contradictory. Material implication is such that 'A ⇒ B' is the same as '¬X ∨ Y'.

Am I missing something?

Then why not reference that in the OP? — Bob Ross

Because I wanted to talk about the question of their contradictoriness without the baggage of the riddle. I think most people got the correct answer, and understood the question, anyway.

I'm not sure what your getting at here. It's not an approximate solution, in the example the program spits out the shortest path between all the nodes, not an approximation. The computation is deterministic. It can only be completed in polynomial time by a non-Nondeterministic Turing Machine, but a deterministic Turing Machine can churn through checking every path, it just takes forever if the input is large.

And the NTM doesn't spit out approximations either, it's just able to take many branching paths through the computation, doing multiple actions based on a single instruction (I was always told to think of this as splitting the NTM into copies in a sort of branching process). People use estimates for these sorts of problems, but that's because they take too long to solve.

...it just takes forever if the input is large. — Count Timothy von Icarus

However, if I includes enough nodes then all of the world's super computers running P(I) until the heat death of the universe still won't have been able to actually compute O yet. — Count Timothy von Icarus

If we have a large number of nodes with infinite time then P(I)=O will produce the ideal solution, it will be unique, and in that case what you conclude no longer holds:

So then, in a very important functional sense P(I) is not "the same thing as O." — Count Timothy von Icarus

If we don't have infinite time then there is no sense in which P(I) is the same thing as O, but if we have infinite time then there is an important sense in which P(I) is the same thing as O.

But my point is that it isn't plausible to compare 2+2=4 to an NP-Complete problem and then claim that 2=2=4 suffers from the same limitations as the NP-Complete problem. 2+2 isn't NP-Complete. The basic objection to your argument would be, "Well I agree that P(I) is not the same thing as O, but it doesn't follow that 2+2 is not the same thing as 4."

Yes, given an "infinite amount of time," or an "eternal realm," it might make sense to think of these relations as eternal. Computation is inheritly stepwise though, so I am not sure this is particularly helpful to do. At any rate, no physical system computes in "no time at all." Human beings stop being able to see expressions as "other names" for their solutions at remarkably low levels of complexity.

Consider: 6X = 1929.121⁸ — (118 + 2/3) 1/918

The value of X is specified here. Is it obvious to you what it is? But surely you know what all the operators are and how to solve for X.

I don't think most people will even be able to glance at 175+39 and instantly tell what number it corresponds to. Hence our intuition that computation is informative

Anyhow, I think the Stroop Test (mentioned earlier) is a better illustration of the way in which cognition relies on communication.