Since I know that this will get lost in the Liar's paradox thread I wanted to separate it out from the thread:(adsbygoogle = window.adsbygoogle || []).push({});

In post 18 of the liar's paradox thread Hurkyl writes:

"and in post #47 he writes: Of course, there are other variations on logic than classical logic. I mentioned computability theory: that the alternatives are {true, false, infinite loop} is rather important to the theory. e.g. it gives a way out to the specific construction of the Liar's paradox I mentioned earlier: to refresh:

Q(R) := not R(R)

P := Q(Q)

The naive implementation of the predicate Q and the sentence P clearly results in P evaluating to "infinite loop".

Hurkyl said: ↑Third, I think it would be interesting to point out that in the logic of computation, there is no problem with there being a sentence P satisfying "P = P is not true". Here's an implementation in python:

however, your computer probably cannot do this computation: an equivalent implementation that will not overflow your stack is:Code (Text):def P():

return not P()

Code (Text):def P():

while True:

pass

I would like to know where he is going with this line of thought. A related concept I've seen before is the concept of bottom:

"In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also called the zero or empty type, and is sometimes denoted with falsum (⊥)."

A function whose return type is bottom cannot return any value. In the Curry–Howard correspondence, the bottom type corresponds to falsity.

http://en.wikipedia.org/wiki/Bottom_type

So while bottom acts like a third truth value, it is actually a subtype of both true and false. So both true and false can be of type Bottom. However, normally both True and False should not be of type bottom unless their is an error in the computation.

To summarize the intent of this thread: How do the laws of logic relate to computation and what deviations might their be from the law of logic (for instance: The law of the excluded middle).

P.S. Also in the Liar's paradox thread the question of the Halting problem came up:

http://en.wikipedia.org/wiki/Halting_problem

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Logic in Computation

Loading...

Similar Threads - Logic Computation | Date |
---|---|

Biocentrism - To me this lacks some logic | Jul 4, 2017 |

Insights Scientific Inference and How We Come to Know Stuff. Part 2 - Comments | Apr 28, 2016 |

Logic puzzle : Smallest number of prisoners required? | Apr 26, 2016 |

Logic & COmputation | Dec 29, 2005 |

**Physics Forums - The Fusion of Science and Community**