• PL Olcott
    626
    Anything that is required to have (simultaneous mutually exclusive properties) cannot exist.
    Requiring a square to be round or a circle to have four equal length sides: a {Square Circle}
    is an example of this.

    It is clear that the impossibility of creating a CAD system that can correctly draw square circles places no limits on what computers can do.

    It is less clear that requiring a program H to report on the behavior of another program D that does the opposite of whatever H says is a logical impossibility when we see that program H1 can correctly say what D will do.

    When we get back to the original {halting problem} we can see that no program H can ever always say what every program D will do because some D will do the opposite of whatever H says.

    So the when the {halting problem} requires a program H to always say whatever program D will do includes programs that do the opposite of whatever H says this is requiring the logically impossible, thus the same as requiring a CAD system to correctly draw square circles.

    The {halting problem} as defined requires the logically impossible therefore it places no actual limits on what can be computed.
  • jgill
    3.8k
    It is clear that the impossibility of creating a CAD system that can correctly draw square circles places no limits on what computers can do.PL Olcott

    Are you referring to Squaring the circle? Are you sure about your opening statement?

    Computer programs can actually do this to any preassigned degree of accuracy. But using only a string compass available to the ancients and a straight edge is impossible in a finite period of time.
  • PL Olcott
    626
    Are you referring to Squaring the circle? Are you sure about your opening statement?jgill

    I am talking about creating a perfectly round thing that
    cannot be round because it has four equal length sides,
    thus a logically impossible square circle.
  • noAxioms
    1.5k
    It is logically impossible to draw a square circle because it must be perfectly round AND not round at all with four equal length sides.PL Olcott
    Not logically impossible. I suppose it depends on your definitions, and 'is perfectly round' is a poor definition of a circle. More like 'all points on a two dimensional surface that are equidistant from the center. Given that and 'four equal sides' (and maybe four equal angles to eliminate a rhombus) as a square, it is not logically impossible.
    Relativity theory ran into that. It proposed something logically impossible, except to somebody who is willing to drop some obvious but unstated premises.

    It is clear that the impossibility of creating a CAD system that can correctly draw square circles places no limits on what computers can do.
    The inability to do an impossible thing isn't a limit? What is 'impossible' if not a limit?

    It is less clear that requiring a program H to report on the behavior of another program D that does the opposite of whatever H says is a logical impossibility when we see that program H1 can correctly say what D will do.
    Godel showed that the program H cannot solve the task to which it is put. You seem to know this since you reference the halting problem. I was just discussing this very thing in another thread.

    So the when the {halting problem} requires a program H to always say whatever program D will do includes programs that do the opposite of whatever H says this is requiring the logically impossible, thus the same as requiring a CAD system to correctly draw square circles.
    Again, I don't find it logically impossible. All you need is to prevent access of H to the inputs of D. This again illustrates the fact that you've presuming conditions which have not explicitly been stated, same as the square circle.

    I am talking about creating a perfectly round thing that
    cannot be round because it has four equal length sides,
    thus a logically impossible square circle.
    PL Olcott
    Agree, squaring the circle is an exercise in what can and cannot be constructed with a compass and straight edge. But the thing you list as impossible can be done, even without drawing a rhombus, which fits your definition of a square.

    Just cut the circle (without moving anything) into four 90 degree arcs. Make them a different color if that helps to visualize it. There you go. Perfectly round figure that is also a figure consisting of four equal length sides. That was really trivial. Point is (the important part): Don't be so hasty to declare something impossible.
  • PL Olcott
    626
    Not logically impossible.noAxioms

    I am not talking about squaring a circle I am talking about drawing a circle that <is> a square thus not a circle. It must be in the same two dimensional plane.

    "all points on a two dimensional surface that are equidistant from the center" and these exact same points form four straight sides of equal length in the same two dimensional plane.

    My notion of {Square-Circle} is the epitome of logically impossible.
  • magritte
    553
    I am talking about drawing a circle that <is> a square thus not a circle. It must be in the same two dimensional planePL Olcott

    On the surface of the Earth, imagine drawing squares centered on the North Pole with increasing length sides until the sides coincide with the circle of the equator. As said ,what can be done is all about unstated presumptions.
  • PL Olcott
    626
    On the surface of the Earth, imagine drawing squares centered on the North Pole with increasing length sides until the sides coincide with the circle of the equator. As ↪noAxioms said ,what can be done is all about unstated presumptions.magritte

    I am trying to form a concrete example of the logically impossible
    changing the subject to the not logically impossible is a strawman rebuttal.
  • noAxioms
    1.5k
    Please show how "all points on a two dimensional surface that are equidistant from the center"
    and these exact same points form four straight sides of equal length in the same two dementional plane.
    PL Olcott
    First you've mentioned 'straight sides'. Also first you've mentioned a 2D plane. This comes back to my point, which you predictably have totally missed besides it being emphasized multiple times: State your premises, because the assessment of 'impossible' or not depends on them.

    I can still do it despite these new definitions.

    On the surface of the Earth,magritte
    Tip O' the hat to magritte, who actually paid attention to my point, and similarly did not see a restriction to Euclidean space, which is interesting because our universe is not Euclidean, so it's not an obvious assumption to make. One can draw a square circle on the 2D closed plane of the surface of (an idealized) Earth. It would have four equal length straight sides.

    changing the subject to the not logically impossiblePL Olcott
    I think only a mod can change the subject of a topic, so it is safe.
    So yes, just be more careful when selecting your logically impossible thing, because so far none of them has qualified. Then, having found some suitable impossible requirement, in order to make your point in the subject line, you need to come up with a scenario that lists it as a requirement. That was also missing in the OP. So let's say for argument sake that a square circle (suitably defined) is impossible. What argument would plausibly list that as a requirement?
  • PL Olcott
    626
    I think only a mod can change the subject of a topic, so it is safe.
    So yes, just be more careful when selecting your logically impossible thing, because so far none of them has qualified. Then, having found some suitable impossible requirement, in order to make your point in the subject line, you need to come up with a scenario that lists it as a requirement. That was also missing in the OP. So let's say for argument sake that a square circle (suitably defined) is impossible. What argument would plausibly list that as a requirement?
    noAxioms

    I did not provided 100% of all of the details of the mathematical definition of a square and a circle so that people having zero knowledge of math would be able to get the gist of my idea. Its really is not that hard to understand that a thing: (that must be round) and (cannot be round) cannot exist.

    Anything that is required to have (simultaneous mutually exclusive properties) cannot exist.
  • Banno
    24.5k
    There's little honour left in these fora.

    Yes, you can't have a plane euclidian shape that is both a square and a circle. And yes, this is because these words do not describe or correspond to anything.

    The sides of 's supposed square do not meet at right angles. Nor is it a plane euclidean shape.

    When such a contradiction is met, one ought go back and check one's assumptions. The assumption that must be rejected in your work is that there can be an algorithm that correctly predicts whether any Turing Machine will halt.

    This thread is a continuation of Self Referential Undecidability Construed as Incorrect Questions.
  • PL Olcott
    626
    When such a contradiction is met, one ought go back and check one's assumptions. The assumption that must be rejected in your work is that there can be an algorithm that correctly predicts whether any Turing Machine will halt.Banno

    When the definition of the halting problem results in requirement that cannot be met because this requirement is a logical impossibility it is this problem definition that must be rejected. The inability to do the logically impossible never derives any limitation on anyone or anything.

    The logical impossibility of solving the halting problem (within its current definition) is exactly the same as the logical impossibility of creating a CAD system that correctly draws square circles.
  • Banno
    24.5k
    It's a reductio. The contradiction you point to is a direct consequence of assuming that the halting problem can be solved. It is what shows that the halting problem cannot be solved.
  • PL Olcott
    626
    ↪PL Olcott It's a reductio. The contradiction you point to is a direct consequence of assuming that the halting problem can be solved. It is what shows that the halting problem cannot be solved.Banno

    When a problem definition requires a logical impossibility then it is the problem definition that must be rejected.
  • Banno
    24.5k


    When an assumption leads to a contradiction, the assumption must be rejected.

    • Assume that there is a solution to the halting problem.
    • Show that this leads to a contradiction.
    • Conclude that there is no solution to the halting problem.
  • PL Olcott
    626
    When an assumption leads to a contradiction, the assumption must be rejected.Banno

    Yes and likewise for any problem definition that requires the logically impossible.

    When we simply drop the requirement that termination analyzer H report on the behavior
    of the directly executed D(D) and instead H reports on D correctly simulated by H then
    the conventional halting problem proofs fail to prove that halting is undecidable.
  • Banno
    24.5k
    Again, it just seems to me that you have misunderstood the structure of Turing's argument.
  • PL Olcott
    626
    ↪PL Olcott Again, it just seems to me that you have misunderstood the structure of Turing's argument.Banno

    When it is understood that requiring the logically impossible is an invalid requirement then the whole notion of undecidability is shown to be incoherent.

    All decision problems that require the logically impossible are thus rejected as incorrect.
  • Banno
    24.5k
    I, and most logicians, agree that
    requiring the logically impossible is an invalid requirementPL Olcott
    and yet see the argument as valid.

    Do you agree that the argument is a reductio? If not, what structure does it have?
  • PL Olcott
    626
    ↪PL Olcott I, and most logicians, agree that
    requiring the logically impossible is an invalid requirement
    — PL Olcott
    and yet see the argument as valid.
    Banno

    An agument cannot possibly be valid if it contains a fatal flaw.
    When-so-ever any decision problem requires the logically impossible
    this decision problem must be rejected as incorrect.
  • Banno
    24.5k
    An agument cannot possibly be valid if it contains a fatal flaw.PL Olcott

    You keep saying that. Sure. Turing's argument is not an example of that. It is a reductio.

    Reductio ad absurdum.

    At least acknowledge that.
  • PL Olcott
    626
    You keep saying that. Sure. Turing's argument is not an example of that. It is a reductio.Banno

    The whole concept of decision problem undecidability is fatally flawed
    because it requires satisfying a logically impossible requirement.


    Instead of determining that some input is undecidable for some decision
    problem we reject the decision problem itself.
  • Banno
    24.5k


    Here it is again:
    The Halting Problem is:

    INPUT: A string P and a string I. We will think of P as a program.

    OUTPUT: 1, if P halts on I, and 0 if P goes into an infinite loop on I.

    Theorem (Turing circa 1940): There is no program to solve the Halting Problem.

    Proof: Assume to reach a contradiction that there exists a program Halt(P, I) that solves the halting problem, Halt(P, I) returns True if and only P halts on I. The given this program for the Halting Problem, we could construct the following string/code Z:

    Program (String x)
    If Halt(x, x) then
    Loop Forever
    Else Halt.
    End.

    Consider what happens when the program Z is run with input Z
    Case 1: Program Z halts on input Z. Hence, by the correctness of the Halt program, Halt returns true on input Z, Z. Hence, program Z loops forever on input Z. Contradiction.

    Case 1: Program Z loops forever on input Z. Hence, by the correctness of the Halt program, Halt returns false on input Z, Z. Hence, program Z halts on input Z. Contradiction.


    End Proof.
    Prof Kirk Pruhs

    I've bolded the assumption for you. It leads directly to the contradiction I've italicised.

    Where's the flaw?
  • PL Olcott
    626
    Where's the flaw?Banno

    The flaw is that the whole notion of decision problem undecidability
    is inherently flawed in that it requires the logically impossible.

    Every undecidable decision problem is simply wrong.

    When I ask you What time is it (yes or no)?
    Does the lack of your correct answer indicate that you are stupid
    or is there something wrong with the question?
  • Banno
    24.5k
    SO there is no identifiable flaw in the argument, yet it is wrong as a whole?

    The flaw is that the whole notion of decision problem undecidability
    is inherently flawed in that it requires the logically impossible.
    PL Olcott

    Does this apply generally? Are all supposed reductio arguments so flawed? They all contain a logical impossibility...

    This by way of pointing out that your argument is not well-formed.
  • PL Olcott
    626
    Does this apply generally? Are all supposed reductio arguments so flawed? They all contain a logical impossibility...

    This by way of pointing out that your argument is not well-formed.
    Banno

    Yes this applies generally. The undecidability of all undecidable decision
    problems is always anchored a the requirement to satisfy a logical
    impossibility.

    Thus the halting problem is analogous determining that computation
    is limited by the failure to satisfy any other logical impossibility such as
    requiring a CAD system to correctly draw a square circle.
  • Banno
    24.5k
    Yes this applies generally.PL Olcott

    To all reductio arguments?
  • PL Olcott
    626
    Yes this applies generally.
    — PL Olcott

    To all reductio arguments?
    Banno

    To all decision problem definitions.

    https://en.wikipedia.org/wiki/Reductio_ad_absurdum
    Finds the logical impossibility thus is fine.

    When it finds a contradiction is derived by a decision problem
    then it is this decision problem that must be rejected.

    When it is contradicted that some H can correctly determine
    the halt status of the direct execution of every D, then this
    definition of the problem is rejected as incorrect.
  • Banno
    24.5k
    When it finds a contradiction is derived by a decision problem
    then it is this decision problem that must be rejected.
    PL Olcott

    Why? Isn't that just special pleading?

    When it is contradicted that some H can correctly determine
    the halt status of the direct execution of every D, then this
    definition of the problem is rejected as incorrect.
    PL Olcott
    Yes, in the example argument above, Z is shown to imply a contradiction, and so is to be rejected.

    That's the reason for rejecting the assumption.

    I dunno. This all appears pretty basic. It still looks to ma as if you have not followed the structure of the argument.
  • PL Olcott
    626
    When it finds a contradiction is derived by a decision problem
    then it is this decision problem that must be rejected.
    — PL Olcott

    Why? Isn't that just special pleading?
    Banno

    When I ask you the question: What time is it (yes or no)?
    it is dead obvious that your inability to provide a correct
    answer is not your fault it is the fault of the question that
    requires a logically impossible answer.

    It is the same for all questions that require logically impossible
    answers and their analog of

    decision problems that have instances of questions that require
    logically impossible answers.
  • Banno
    24.5k
    And, again, where does such a question occur in the example?

    Seems to me to be in Z; the contradiction that is used to deny the assumption.

    But I don't know what you think here.

    In the other thread I suggested that the analogue would be "Will Program Z loop forever if fed itself as input?"
  • Banno
    24.5k
    ...and the trouble with that is that there doesn't seem to be any obvious problem with Z.

    So the problem must be H.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment