Can a Computer Recognize a Paradox?

[Keln]

Simple question: Can a computer be taught to recognize a paradox?

This assumes the computer has no cognizant reasoning or "self awareness".

It is a plot device used in a lot of science fiction, that the intrepid "flawed" human hero defeats the computer or robot with a simple paradox making it smoke and spark and such nonsense because it can't escape a paradox.

Can a computer be taught or programmed to recognize and simply brush aside such a thing? Or does that actually require reasoning skills?

 

[Filip Larsen]

Presenting logical contradicting data to a computer in hope of making it go up in smoke is mostly a story telling device that I would guess stem from the "golden years of AI" [1] where future intelligent machines where thought to be based on logical reasoning. There is no fundamental problem for software to handle any kind of data, including logical contradicting data, but it of course requires that the software is designed to do so.

At best you can compare it to present days vulnerabilities in software that allow special designed data to perform a denial-of-service attack [2] or similar exploits. However, those vulnerabilities are mostly due to subtle mistakes and flaws in the software and not because of any fundamental inability to handle logical inconsistent data.

[1] http://en.wikipedia.org/wiki/History_of_artificial_intelligence
[2] http://en.wikipedia.org/wiki/Denial-of-service_attack

 

[Fooality]

I've actually thought about this one a bit. The key thing about paradoxes is that they are inconsistent given assumptions you throw at them. So take some statement that's not a paradox: 2+2=4. Assume it is true, no contradiction will result, everything works. Assume its false, contradictions will result. Now take a paradox, for instance the simple statement "this statement is a lie". If you assume the statement is true, it follows that its false. If you assume its false, it follows (via excluded middle) that its true. Logical contradictions with either assumption. You can also imagine statements which are consistent under any assumption like geometry is with or without the parallel postulate, basically logical tautologies instead of contradictions.

But the point is, you can see all truth values as unary logical functions acting on their assumptions: True outputs True regardless of your assumptions, False outputs False regardless of your assumptions. But a paradox is equivalent to the NOT function, reversing your assumptions either way, and a tautology is equivalent to an identity function, confirming your assumptions either way with a consistent system. So using this method to test assumptions, a computer should be able to identify them.

 

[rcgldr]

You could think of a process to deal with a paradox as a means to test possible results and eliminate the results that don't work, and if all possible results are eliminated, then conclude the problem statement is self conflicting. So in the case of "this statement is a lie", the process eliminates both "true" and "false", and then determines that the statement is self conflicting. So the potential weakness here is not programming the process to check for inconsistencies like self-conflicting statements.

 

[Fooality]

You could think of a process to deal with a paradox as a means to test possible results and eliminate the results that don't work, and if all possible results are eliminated, then conclude the problem statement is self conflicting. So in the case of "this statement is a lie", the process eliminates both "true" and "false", and then determines that the statement is self conflicting. So the potential weakness here is not programming the process to check for inconsistencies like self-conflicting statements.

Yeah, good point, I guess that's why the scifi works: No matter what a computer can theoretically do you can never rule out programmer error. But its an interesting question, and I don't know the answer rigorously. Is there some way to hijack the system we're talking about, and inject some set of statements that would mess up it? I don't know.

 

[DaveC426913]

The idea of a computer smoking and sparking because it encounters a programming problem would be a fatally hackneyed element in your storywriting - equivalent to rockets dangling from strings or hearing explosions in space.

Be original.

Does the computer have any control over its environment? What if it had to activate the sprinkler system to save itself from a fire, knowing it would get shorted out? (Even this is hackeyed, as well as flawed: no systems designer would set up a system like this.)

Asimov was adept at creating logical flaws that paralyzed his robots. For him, with his 3 laws, all he had to do was set up a circumstance where the robot thought a person was going to get hurt if it didn't act by sacrificing itself.

 

[Keln]

Thanks for the replies. The idea about testing inputs for flawed logic makes sense. Bad data can be filtered and ignored. I don't suppose a computer/robot could be programmed to recognize a paradox as such, since that seems to require abstract thinking and the ability to consider something illogical, but it seems sensible that it could just ignore what it doesn't understand and move on.

Dave - I am not writing any scifi stories, but if I ever did I would never dream of adding the sparking and smoking computer thing. I just used that as an example of (admittedly old) sci fi elements that demonstrate the whole paradox vs computer thing. I've only seen smoke from a computer once, and it was due to a power supply failure.

My curiosity on the topic is mostly in the question of where the boundaries are between what programming can do, and what it cannot.

 

[Carno Raar]

First Controller

In response to your concern that our autonomous exploration space-craft could be disabled by a logical paradox, I must assure you that the Autonomous Control System (ASC) of all Frob Empire Scout Ships consists of multiple flight control computers, none of which are identical, and that these computers vote on which actions to take. An enemy or anomalous event would therefore have to disable multiple computers of different designs and software.

In addition there exists a fallback mode that is activated when the system suffers unrecoverable failure of the ACS. Each ACS computer periodically sends a keep-alive signal to the Recovery Mode Controller. In the event of an ACS computer being lost or hung, it will no longer be able to transmit this signal. The Recovery Mode Controller is therefore able to detect when the ACS is no-longer viable, and will attempt to reset and reboot ACS computers as required. If the ACS cannot be restored because fewer than 3 computers are available, it will automatically take action, using un-alterable stored procedures, to return the vessel to the nearest starbase, or self-destruct if such an action proves impossible.

 

[Fooality]

Thanks for the replies. The idea about testing inputs for flawed logic makes sense. Bad data can be filtered and ignored. I don't suppose a computer/robot could be programmed to recognize a paradox as such, since that seems to require abstract thinking and the ability to consider something illogical, but it seems sensible that it could just ignore what it doesn't understand and move on...

Yeah, the main thing I see is it can recognize the damage a paradox does to a set of statements and discard it, which is pretty similar to what our brains do. Consider Curry's paradox, in the context of a conversation:

"If what I'm saying is true, Obama is Elvis."
"You're full of it, Obama is not Elvis."
"I'm not saying he is, I'm just saying if what I'm saying is true, Obama is Elvis"
"But what you're saying is not true"
"I'm not even saying that what I'm saying is true, I'm saying IF what I'm saying is true, than Obama is Elvis. Can you admit that simple statement is true?"
"Okay, big IF there, but sure."
"So you admit that statement is true, and therefore that Obama is Elvis!"

Would that argument ever convince you? No, because it contradicts a load of other things you know to be true about the world, its not consistent with other facts. A computer system can always do the same, and see when the logical consequences of a statement break a bunch of other things, and decide therefore to discard the statement.

 

[Svein]

Simple question: Can a computer be taught to recognize a paradox?

... but mathematicians can! A paradox is the basis for Gödel's incompleteness theorem.

 

[kroni]

If your mind can escape paradox, a computer can make it too. Because a computer can simulate a physical system then can simulate a brain, then escape the paradox.

 

[Keln]

If your mind can escape paradox, a computer can make it too. Because a computer can simulate a physical system then can simulate a brain, then escape the paradox.

That sort of creeps into the central point of why I am asking my question. If a computer can be built that can simulate a physical brain, does it then cease to be limited by its programming and is now sentient? How far can programming actually go? Can it really simulate thinking? Can a machine be programmed to consider illogical things? Can it be programmed to "think outside of the box"? Is a simulation of the human mind simply a matter of processing power, or is there a hard limit to what a machine could ever be programmed to do?

 

[Svein]

That sort of creeps into the central point of why I am asking my question. If a computer can be built that can simulate a physical brain, does it then cease to be limited by its programming and is now sentient? How far can programming actually go? Can it really simulate thinking? Can a machine be programmed to consider illogical things? Can it be programmed to "think outside of the box"? Is a simulation of the human mind simply a matter of processing power, or is there a hard limit to what a machine could ever be programmed to do?

A collection of good questions. My answer is: It depends on the system architect/chief programmer.

 

[kroni]

We are very very very very very very very far of doing something intelligent with a computer.
Trust me, computer, programming tools and processing power are not ready.
I propose to wait a century and speak about again.

 

[Carno Raar]

We are very very very very very very very far of doing something intelligent with a computer.
Trust me, computer, programming tools and processing power are not ready.

According to wikipedia, a fly has 10⁵ neurons and 10⁷ synapses. AI is not my field but computing is, and I know we can build that, and have built larger simulations. The fact that it doesn't work is more a lack of understanding than a lack of computing power.

On the original topic, we have formal logic systems that can correctly identify a paradox. If an AI is a computer program, even if it can't program itself, then there's nothing stopping it using a second computer to run existing software. More likely it'll just be given a bigger computer with the option to use part of it to run whatever existing programs it needs.

 

[Fooality]

According to wikipedia, a fly has 10⁵ neurons and 10⁷ synapses. AI is not my field but computing is, and I know we can build that, and have built larger simulations. The fact that it doesn't work is more a lack of understanding than a lack of computing power.

...

That's a really good point. Another open question is if someone did find the actual complete simulation of brain activity, would it have a computational reduction that could dramatically speed it up, just a little too complex to have been arrived at by evolution? Its totally possible, and that means incredible AI could exist on current hardware.

 

[kroni]

Computer intelligence can occur by evolution, a program compile it's own source code, you introduce a mutation factor, with a very good luck you evolve to perfect intelligence. This process have nothing comparable to number of neuron, the probability, and the bootstrap of the optimisation need a extreme computer power. Not compatible with our computer. We are not ready for emergent life on device.

 

[meBigGuy]

http://www.artificialbrains.com/
BlueBrain Project:
As of November 2011 the largest simulations were of mesocircuits containing around 1 million neurons and 1 billion synapses. A full-scale human brain simulation of 86 billion neurons is targeted for 2023.

Might be a while before it is real time.

Also
http://www.gizmag.com/openworm-nematode-roundworm-simulation-artificial-life/30296/

 

[DaveC426913]

That sort of creeps into the central point of why I am asking my question. If a computer can be built that can simulate a physical brain, does it then cease to be limited by its programming and is now sentient? How far can programming actually go? Can it really simulate thinking? Can a machine be programmed to consider illogical things? Can it be programmed to "think outside of the box"? Is a simulation of the human mind simply a matter of processing power, or is there a hard limit to what a machine could ever be programmed to do?

It's pretty difficult to define the line between non-sentience and sentience, but there are practical ways to answer your question.

Any program that is complex enough is able to make decisions such as "I choose not to follow this illogical line of thought." Or more simply: "I choose not to obey you."

 

[meBigGuy]

It's pretty difficult to define the line between non-sentience and sentience, but there are practical ways to answer your question.

Any program that is complex enough is able to make decisions such as "I choose not to follow this illogical line of thought." Or more simply: "I choose not to obey you."

As we delve into the philosophical... Choosing to not obey can be a simple reasoning process, like "If it is Monday, ignore input saying to turn off"

Saying "I choose", accent on "I", now that is significant.

I think a significant milestone would be awareness of being aware.

Going back to the OP, I initially thought "hey that's simple - just keep track of logical conclusions and if you come back to a previous one, take a different path or conclude it is circular or contradictory." But, how to program that in a general sense is difficult to visualize.

THis page http://www.philosophybasics.com/branch_logic.html has a section on paradoxes.

" It can be argued that there are four classes of paradoxes:

• Veridical Paradoxes: which produce a result that appears absurd but can be demonstrated to be nevertheless true.
• Falsidical Paradoxes: which produce a result that not only appears false but actually is false.
• Antinomies: which are neither veridical nor falsidical, but produce a self-contradictory result by properly applying accepted ways of reasoning.
• Dialetheias: which produce a result which is both true and false at the same time and in the same sense.

Paradoxes often result from self-reference (where a sentence or formula refers to itself directly), infinity (an argument which generates an infinite regress, or infinite series of supporting references), circular definitions (in which a proposition to be proved is assumed implicitly or explicitly in one of the premises), vagueness (where there is no clear fact of the matter whether a concept applies or not), false or misleading statements (assertions that are either willfully or unknowingly untrue or misleading), and half-truths (deceptive statements that include some element of truth)."

 

[Fooality]

As we delve into the philosophical... Choosing to not obey can be a simple reasoning process, like "If it is Monday, ignore input saying to turn off"

Saying "I choose", accent on "I", now that is significant.

I think a significant milestone would be awareness of being aware.

Is it though? If a computer comes to a decision through a reviewable deterministic process, that can't be called a choice. But if the process leading to the decision is unknown, than it can be called a choice. If we logically conclude that we must have the salad not the doughnut to stay within our diet goals, we say "I have no choice but to take the salad". If there are no such goals but a random whim makes us pick the salad, we say we chose it. Is it so different for a computer? I think as you start bringing in things are mysterious in their nature, like the collapse of a qubit through observation, to drive computational processes, than the language of choice becomes inevitable.

Quantum computers will choose outcomes, because there's no other language to describe an observable deterministic process that dictates their actions, because none exists.

 

[meBigGuy]

This is a bit off-topic.

I think maybe you misunderstand quantum computing. Have you ever programmed one? They are perfectly deterministic.
http://en.wikipedia.org/wiki/Quantum_programming.

BTW, "the collapse of a qubit through observation" is pretty old school (try Copenhagen)

 

[Carno Raar]

Copenhagen hasn't yet been invalidated.

 

[meBigGuy]

I never suggested Copenhagen might be invalid, just that, conceptually, "collapse", as a term, is a bit old school compared to decoherence.

I wouldn't be so bold as to say that ANY interpretation is invalid. Just in-favor, out-of-favor, etc. Subjective opinions.

 

[Fooality]

This is a bit off-topic.

I think maybe you misunderstand quantum computing. Have you ever programmed one? They are perfectly deterministic.
http://en.wikipedia.org/wiki/Quantum_programming.

BTW, "the collapse of a qubit through observation" is pretty old school (try Copenhagen)

Huh? From the article on quantum computing:
http://en.wikipedia.org/wiki/Quantum_computing
"Quantum algorithms are often non-deterministic, in that they provide the correct solution only with a certain known probability."
Quibits can be prepared in states where they collapse in one way or another with high probability, but they can also be prepared in states where they collapse in one way or another with any probability. Quantum computing is fundamentally probabilistic, and deeply tied to randomness. One of my favorite reads on it:
http://www.americanscientist.org/issues/pub/the-square-root-of-not
Quantum computing includes gates which who's outputs are completely uncorrelated with their inputs, pure randomness. Chaining two of these gates makes a classical not gate.

 

[meBigGuy]

From the same wikipedia article, however:

Given sufficient computational resources, however, a classical computer could be made to simulate any quantum algorithm, as quantum computation does not violate the Church–Turing thesis.

Also, a classical computer can easily achieve true randomness by sampling an analog noise source.

Philosophically it boils down to: (from http://en.wikipedia.org/wiki/Church–Turing_thesis)
---------------------------------------------------------------------------
Philosophical implications
Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind; however, many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement.[53] B. Jack Copeland states that it's an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical question whether any such processes are involved in the working of the human brain.[54] There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:

1. The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis and is a foundation of digital physics.
2. The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category. The assumption that incomputable physical events are not "harnessable" has been challenged, however,[55] by a proposed computational process that uses quantum randomness together with a computational machine to hide the computational steps of a Universal Turing Machine with Turing-incomputable firing patterns.
3. The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and Roger Penrose[56] have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation, although there is no scientific evidence for this proposal.

There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
----------------------------------------------------------------------------
I learn something every day.
Not sure how this helps us detect a paradox.

 

[Fooality]

From the same wikipedia article, however:

Given sufficient computational resources, however, a classical computer could be made to simulate any quantum algorithm, as quantum computation does not violate the Church–Turing thesis.

Really interesting stuff you bring up there. But what's hitting me right now, so I'll just say it, is that the statement above simply has to be wrong. The reason I say this comes from the work of Chaitin, which I remember as saying that a truly random sequence of numbers must be incompressible. In other words, the only randomness a classical deterministic computer can output is pseudo-randomness, because it comes from a deterministic program of finite length...Its compressed into that program, so not truly random. True randomness, as you would get (I suppose) from observing an endless series quibits prepared in the 50% one way 50% the other state, would have an output that could only be simulated by Turing machine with a tape of infinite length, with random digits written on it all the way down recording those outcomes. I guess its legal, because we allow Turing machines to have tapes of infinite length, but it really strikes me as an abuse of the idea, and has no correspondence to any real world computer, which are deterministic.

Its true what you say about taking inputs from an analogue source, but this introduces randomness, possibly quantum into the mix, and makes the computer capable of acting in a non-deterministic way, so its not a Turing machine.

edit: A classical computer (Turing Machine) can sure emulate the probabilities of the outcomes of a quantum computer, so in the case of above program it outputs 50% over and over, but it can't emulate the actual outputs, which is a pretty big thing when it comes to stuff like quantum evolutionary algorithms.

 

[meBigGuy]

I'm a little over my head with turing-not_turing. A turing machine acting on external input is not turing? You're assuming the computer itself has to be not-deterministic. Of course, if you are asking whether the Universe is turing, I guess that precludes IO.

 

[Fooality]

I'm a little over my head with turing-not_turing. A turing machine acting on external input is not turing? You're assuming the computer itself has to be not-deterministic. Of course, if you are asking whether the Universe is turing, I guess that precludes IO.

Yeah, I think its an area where it pays to be really clear on what we mean. The definition of determinism from the Wikipedia page says:

Determinism is the philosophical position that for every event, including human action, there exist conditions that could cause no other event.

So Turing machines are deterministic in that the same input for the same program always should create the same output. Quantum theory has been called "The Death of Determinism", because it only gives probabilistic explanations, while recognizing outcomes that are fundamentally random. Now there is some shiftiness in that term though, because in Computer Science, we learned about deterministic and non-deterministic finite automata, (DFA, NFA) and that every NFA can be simulated by a DFA was the claim I recall, but it was a straight up different definition of non-determinism in computer science, in which every possible path was explored, vs just one. If you mapped it to quantum mechanics, it would be like embracing many-worlds-interpretation, and saying if in some universe a solution is found, that's good enough. But in the real world we are stuck with the solution we are presented in this universe/world, and in many cases its basically random which we get.

So the bottom line is, quantum systems, like a quantum computer, simply cannot be simulated deterministically, without a hidden variables theory of QM, no matter how much computer resources we have. That's my claim and I'm sticking to it.

edit: Just a thought to add to this. Deterministic behavior is a subset of quantum behavior, (Quantum computers can simulate classical ones, and converge out of the randomness to classic answer) so a really robust implementation of something like Shor's algorithm, that practically always gives the same outputs for its input, (deterministic in this regard) probably always can be implemented by a classical computer. But many other quantum programs cannot, and even quantum programs that always give the same output for a given input may not be classically simulated if they use true incompressible quantum randomness somehow to arrive at their answer.

 

[meBigGuy]

Is a digital system with a random quantum IO value turing? You are saying it is not a turing system because because it is not repeatable, but if you include the IO value as part of the system, it is perfectly repeatable. The quantum not gate is certainly simulatable and can give a perfectly random value for the observation of its midterm of you have access to random IO. You cannot finitely and digitally simulate a random IO, but I don't think that is the issue.

You can say that a quantum system is not simulatable by a purely digital system. But I have a problem with classifying a deterministic digital system with access to true randomness as not deterministic. (depends on your frame of reference?)

But, didn't this start by the inference that high AI is needed to ferret out a paradox? I don't think that is the case.

 

[Fooality]

Is a digital system with a random quantum IO value turing? You are saying it is not a turing system because because it is not repeatable, but if you include the IO value as part of the system, it is perfectly repeatable. The quantum not gate is certainly simulatable and can give a perfectly random value for the observation of its midterm of you have access to random IO. You cannot finitely and digitally simulate a random IO, but I don't think that is the issue.

You can say that a quantum system is not simulatable by a purely digital system. But I have a problem with classifying a deterministic digital system with access to true randomness as not deterministic. (depends on your frame of reference?)

But, didn't this start by the inference that high AI is needed to ferret out a paradox? I don't think that is the case.

Yeah the thread is drifting a little bit at this point, but its interesting to me. As to your problem, yes most certainly: if several hours of digital input from a security camera are the inputs to a computer program that processes them, its certainly deterministic, in that those same several hours of footage will always get the same output from the same program. However, if we move the border of the system out to the front of the security camera, and we say that the same light fields that occurred in front of the camera for the first several hours will appear again exactly the same, the digital input will probably be different this time, because now quantum effects of light are at play, and the ways the exact same probability wave functions of the exact same light fields collapse will be random and different due to quantum law. So once you bring that tiny bit of randomness in, the whole system is now non-deterministic. So yeah, its about where you draw the boundary, maybe that's what you meant by frame of reference.

As far as the paradox issue, Jesus... the OP sent me on a line of research that blew up my mind and has me reeling. I suspect you're right... but man, there's some weird stuff surrounding paradoxes.

 

[Czcibor]

Shouldn't paradox be treated under exception handling? I mean treat it as usual case when something is wrong with data / function and just try to resume operation anyway?

I mean for practical reasons an AI may face imperfect data input all the time. Realistic approach involves some default workaround function.

 

[D H]

Simple question: Can a computer be taught to recognize a paradox?

No. At least not always.

I'm surprised that after 32 posts, no one has mentioned the halting problem.

from halting import returns
# The halting module provides functions that analyze python programs and
# functions for infinite loops and related problems.
# The function halting.returns(f) returns
# - True if the function f returns in finite time,
# - False otherwise.

def all_cretans_are_friendly() :
    while returns(all_cretans_are_friendly) :
        print ("Hello!")

How many times does all_cretans_are_friendly print "Hello!"? Zero times? An infinite number of times? Something else?

If the function enters the loop, it will stay in the loop, printing "Hello" forever and ever. The function won't return, so halting.returns(all_cretans_are_friendly) must return False. But then all_cretans_are_friendly never enters the loop, in which case halting.returns(all_cretans_are_friendly) must return True. But then all_cretans_are_friendly must loop forever. A paradox!

The function halting.returns cannot exist. The halting problem, or anything equivalent to it, is undecidable by a Turing machine. There are a number of problems in computer science that are equivalent to the halting problem. Rice's theorem says that any non-trivial question about a computer programming language is undecidable because any non-trivial question is equivalent to the halting problem.

 

[Fooality]

No. At least not always.

I'm surprised that after 32 posts, no one has mentioned the halting problem.
...

You make good points there, but ultimately you're right: The returns() function can't exist, that's all there is to it. Assuming that function exists creates a contradiction, assuming it does not exist does not, so it does not exist, Once you accept that fact, as everyone does, there is no paradox, just a reference to a non-existent function. What I'm not seeing (and maybe I'm being foggy) is does this directly applies to recognizing logical paradoxes? I just don't know, it might.

I was actually looking into something similar before this post even came up, with Kolmogorov complexity. My question was here:
https://www.physicsforums.com/threads/help-with-kolmogorov-complexity-proof.811244/
You have a similar situation, where the kolmogorov() function can't exist as a computable function. The weird thing is, my program I describe in that post, will always calculate the correct answer to the kolmogorov() function in finite time, it just can't return it because it doesn't know when its computed it. That was confusing me. Its the computer version of the Berry Paradox. I can wave my hand at the Berry Paradox, but once you see it in computational form, its so solid and so damned weird. There basically expressions that clearly have solutions which are singular, simple numbers, but if you know what they are with certainty, math collapses with a paradox. Its so weird at this point I'm just standing back and saying "Woah".