An Impossible Machine

It's impossible to create a machine that would tell for every statement whether it's true or false.

Yes, indeed. What would machine say given the following self-referential sentence?

This machine will not say that this sentence is true.

The machine can't say that the sentence is true for this would contradict the sentence. The machine can't say that the sentence is false either for then the sentence will be actually true in contradiction with the machine's assertion.

Therefore, if the machine existed, it would not be able to pass a judgement on the sentence. Therefore, the sentence would be essentially true but the machine would not be able to tell either way.


Rino Caputo had this to remark:

"It's impossible to create a machine that would tell for every statement whether it's true or false".

Yes, you are right, but it is not a matter of "machines"; in fact, even for a "human being" it will be impossible to tell whether it's true or false for any sentence like "I'm lying".

Here is my reply:

Dear Rino:

You are of course right. But there is a difference between referring to a machine or to a human. Implicitly, a machine can't be illogical while a human may.

For example, in To Mock a Mockingbird, R. Smullyan considers this question (in the very beginning of the book):

"There is a question I could ask you that has a definite correct answer - either yes or no - but it is logically impossible for you to give a correct answer. You might know what the correct answer is, but you cannot give it. Anybody other than you might possibly be able to givethe correct answer, but you cannot!"

The question is "Is no your answer to this question?"

Two remarks are pertinent in this context:

  1. As before, humans may be illogical. Do you want me to utter the answer to Smullyan's question all logic notwithstanding? Watch me. For a machine, on the other hand, knowing but being unable to communicate the answer is a contradiction anyway. Have you read "Liar!" by I. Asimov? This is exactly the situation.

  2. With all advances in medicine, we are not in a position to create humans with prescribed behavior. While the same is true of machines, speculating that it might be possible after all seems less ambitious than it would be with the production of humans by design.

Sincerely,
Alexander Bogomolny

Lars Eriksson ruffles my feathers:

Sorry to bother,

but I could'nt find a place to add a comment to the site, so Take it or leave it.

About the section It's impossible to create a machine that would tell for every statement whether it's true or false. I agree with this statement but not the arguments.

Rino Caputo example "This machine will not say that this sentence is true."

If the machine say "true" it would only say that it "will not say that this sentence is true". The sentence in itself may be true or false, but if it returns "true" it certainly says the statement is true. If the statement is true or false and refers the properties of the machine, the machine can accordingly return true or false. Compare to an electronic gate; It gets true or false as input it returns true or false depending on its properties (if it's an AND, OR, NAND etc.)

Your reply "Is no your answer to this question?"

If the machine say "no" (or false) I would say it's a "double negation" (direct translation from swedish; don't know if it translates) i.e. "yes" (or true). Notice the difference. Rinos example is a statement while yours is a question.

The problem with the examples are that they refer to themselves. I just read a book where Gödel's work was examplified with the following sentence "To this statement, there is no evidence". Suppose it was possible to find out if an evidence existed for the statement (without finding the evidence), this would allow us to answer true or false to the sentence but still, we could say nothing about if the the statement mentioned within the sentence was true or false.

Thanks for a nice web-page
Lars Eriksson

And here's a remark from Aggelos Andreou, Greece:

Hello Alexander,

The sentence "This machine will not say that this sentence is true." is neither true or false until the machine answers it. As long as the machine does not answer, the sentence is not false, but on the other hand it will become true after an infinite amount of time elapses. So I think the problem is not with creating the machine, but that not all sentences have a logical true or false value.

Maybe this is more obvious with the next sentence: "This machine will not say, within the next 1 hour, that this sentence is true." Until the 1 hour elapses none can say that this sentence is true or false. Only after the time elapses or the machine answers within the 1 hour, the sentence receives a true or false value. So such a machine will think and think until the predefined amount of time elapses (in the first sentence case will think for ever) and then will say that the sentence is true. Someone could argue that the constructor of the machine, knowing how the machine works, can tell that the sentence is true before the time elapses, but this is just a predection and not the logical value of the sentence.

My Best Regards,
Aggelos.

Terry Wight argues that a question that may be impossible to answer with a simple yes or no, may succumb to a more extensive answer:

Hi Alexander,

I was reading, with great interest, some of the impossibilities you describe on your Web site.

It's all quite fascinating. Thanks for spending the time to create and share this fun stuff.

The most fun part for me is in discovering that you are inaccurate when you say "There is a question I could ask you that has a definite correct answer - either yes or no - but it is logically impossible for you to give a correct answer."

"Is 'no' your answer to this question?" can be answered correctly with "'No' is my answer to that question." or "My answer is 'no'."

It's not impossible unless the person being asked voluntarily restricts themself to the answer set {yes, no}.

Regards,

Terry Wight

I think that, perhaps, "Yes, 'No' is the answer to that question" is even better.

References

  1. Rudy Rucker, Infinity and the Mind, Princeton University Press, Princeton, NJ, 1995

Self-reference and apparent self-reference

  1. Does It Blink?
  2. Apparent paradox
  3. Set of all subsets
  4. An Impossible Page
  5. Russell's paradox
  6. An Impossible Machine
  7. A theorem with an obvious proof
  8. The Diagonal Argument
  9. A link to a very similar puzzle

|Contact| |Front page| |Contents| |Algebra| |Impossible|

Copyright © 1996-2018 Alexander Bogomolny

71471484