wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Universal Truth Machine
        
(Message started by: jkemp on Aug 8^th, 2002, 1:25am)

Title: Universal Truth Machine
Post by jkemp on Aug 8^th, 2002, 1:25am

"Someone claims to have invented a Universal Truth Machine (UTM), a machine that can correctly answer any question. Devise a question that the UTM cannot correctly answer, thereby disproving the inventor's claim."

(highlight text below to reveal my answer)
"Is this statement false?"
(/answer)

******************************************
NOTE FROM ADMIN 6:15 PM 8/8/2002:
Problem now modified so it's not so trivial:

Someone claims to have invented a Universal Truth Machine (UTM), a machine that takes a proposition as input, and returns "true", "false", or "undecidable" as output.

Devise a true proposition that the UTM will claim to be false, thereby disproving the inventor's claim.

Title: Re: Universal Truth Machine
Post by bartleby on Aug 8^th, 2002, 9:49am

Yes, this is pretty much the standard NP-completeness conundrum... Originally phrased as "Can you write some software that takes as input a computer program, and will tell you 'yes' or 'no' whether or not that computer program will halt, given a certain input." Or the Godel-number problem.

Actually... how come the UTM couldn't respond to your question with the answer "Meaningless" or "Unknowable"??? :)

Title: Re: Universal Truth Machine
Post by Jonathan_the_Red on Aug 8^th, 2002, 9:59am

Followup:

After you point out the flaw in the UTM, the disappointed inventor follows Bartleby's suggestion and modifies the machine so it prints "unknown" for certain problems it's unable to answer.

A few years later, the inventor proudly unveils the Advanced Universal Truth Machine (AUTM). The way it works is: you give it a question, and it prints out "yes" if the UTM can answer the question, and "no" if the UTM cannot. For example, if you say "Does two plus two equal five?" to the AUTM, it will print out "yes" (because the UTM will correctly answer "no" to that question), and if you say "Is this sentence false?" to the AUTM, it will print "no".

Give an example of a statement the AUTM cannot answer.

Title: Re: Universal Truth Machine
Post by AlexH on Aug 8^th, 2002, 12:08pm

Technical quibble: Bartleby I think you mean undecidability or incompleteness. Any NP-complete problem is decidable and would be correctly answered by the UTM.

Title: Re: Universal Truth Machine
Post by Eric Yeh on Aug 8^th, 2002, 1:24pm

Jon,

How about, "does the first 0 of Chaitin's constant occur at an even index?"

:D

Title: Re: Universal Truth Machine
Post by william wu on Aug 8^th, 2002, 3:39pm

I think I have revised the problem so it's not so trivial anymore (maybe?):

Someone claims to have invented a Universal Truth Machine (UTM), a machine that takes a proposition as input, and returns "true", "false", or "undecidable" as output.

Devise a true proposition that the UTM will claim to be false, thereby disproving the inventor's claim.

So statements such as: "This sentence is false" no longer suffice, because the machine would just return "undecidable", which is the correct response.

Title: Re: Universal Truth Machine
Post by Jonathan_the_Red on Aug 8^th, 2002, 3:45pm

"This statement is undecidable?"

Title: Re: Universal Truth Machine
Post by jeremiahsmith on Aug 8^th, 2002, 4:36pm

on 08/08/02 at 15:45:47, Jonathan_the_Red wrote:

"This statement is undecidable?"

No, because that statement could correctly be considered false.

Title: Re: Universal Truth Machine
Post by Jonathan_the_Red on Aug 8^th, 2002, 4:49pm

Duh. Oops.

Title: Re: Universal Truth Machine
Post by jkemp on Aug 8^th, 2002, 5:29pm

How about: "The Universal Truth Machine is not infallible."

The assumption is that this statement is true;
however, the UTM believes it is infallible, so will say this statement is false (because its maker programmed it to be infallible).

Title: Re: Universal Truth Machine
Post by jeremiahsmith on Aug 8^th, 2002, 5:35pm

on 08/08/02 at 15:39:09, william wu wrote:

Devise a true proposition that the UTM will claim to be false, thereby disproving the inventor's claim.
[/color]

Well, the only way this could work, as far as I can see, is if the machine isn't omniscient. Thus, you would simply make a statement whose answer is outside the realm of its knowledge. Let's say I said "Your inventor is dead." Now, as far as the machine knows, its inventor is still alive and kicking, so it'll say that it's "false". But what the machine doesn't know yet is that its creator kicked the bucket a half hour earlier, so it said a "true" statement was "false".

But this isn't so much a statement on the ability to evaluate statements for truth value, as it is on how much truth the machine knows. I mean, if the machine doesn't know math, it can't say "0 + 2 = 5" is false.

Title: Re: Universal Truth Machine
Post by jkemp on Aug 8^th, 2002, 5:40pm

I think one of the assumptions is that the machine will answer "undecidable" for questions it cannot know; e.g. if it does not have access to the births&deaths section of the local paper it will not know if its inventor has died.

On the other hand, one could assume that the UTM is so advanced it keeps track of everything in the world, through various means. E.g. it maintains a connection to the Internet, hacks into satellite networks, maybe even sends out probes or droids to gather information for itself (I'm starting to recollect a Superman movie where the computer becomes sentient and starts to take over the world :-/), so it pretty much knows anything we can know.

Title: Re: Universal Truth Machine
Post by jeremiahsmith on Aug 8^th, 2002, 5:43pm

on 08/08/02 at 17:29:27, jkemp wrote:

But "The UTM is fallible" an assumption, not the truth. Plus, you're also assuming the UTM has knowledge of its own fallibility.

Title: Re: Universal Truth Machine
Post by jkemp on Aug 8^th, 2002, 5:48pm

> But "The UTM is fallible" an assumption, not the truth. Plus, you're also assuming the UTM has knowledge of its own fallibility.

Ok, good point; but I think the UTM should have knowledge of its own abilities. Here's a different explanation:

My statement "The UTM is fallible" is true, provided that the UTM answers "False". If the UTM were to answer "True" or "Undecidable", that would itself contradict the maker's claim (that the UTM is infallible).

Title: Re: Universal Truth Machine
Post by jeremiahsmith on Aug 8^th, 2002, 5:51pm

on 08/08/02 at 17:48:07, jkemp wrote:

My statement "The UTM is fallible" is true, provided that the UTM answers "False". If the UTM were to answer "True" or "Undecidable", that would itself contradict the maker's claim (that the UTM is infallible).

Well, yes, you would still condemn the inventor to a life of destitute shame...but the question is technically asking for a true statement that would evaluate to false, not to simply prove that the UTM doesn't always work.

Title: Re: Universal Truth Machine
Post by tim on Aug 8^th, 2002, 7:28pm

The problem has no solution.

The inventor could (incorrectly) claim that a machine is a UTM even if it returns true all the time. Since it always returns true, you will never find a proposition to which it will incorrectly return false.

We need more constraints on the behaviour of the UTM to rule out such possibilities.

A general solution to most such UTM problems is "A true UTM cannot assert that this proposition is true". If a purported UTM returns true, then it is asserting that it is not a true UTM. A true UTM cannot assert that it is not a true UTM. So the proposition is true. Not undecidable, but true.

A false UTM can assert whatever it likes.

Title: Re: Universal Truth Machine
Post by anshil on Aug 8^th, 2002, 9:59pm

What is the answert to the ultimate question of life, universe and everything?

Title: Re: Universal Truth Machine
Post by Archon on Aug 9^th, 2002, 7:22am

Instead of asking it for an answer that may or may not be beyond its knowledge, ask it (or make propositions to it) about its knowledge directly.
"There is nothing that you do not know". Or variants. Such a proposition is certainly not undecidable (has an actual true or false answer), but the machine cannot know of that which it does not know, and therefore cannot answer "true". If it answers false, then it is not actually a UTM. I see that this is a variant of Tim's answer, but I cannot devise a question/statement to which it will actually answer incorrectly, only questions/statements that prove it does not, in fact, know the answer to every question.

Title: Re: Universal Truth Machine
Post by Mongolian_Beef on Aug 13^th, 2002, 10:33pm

I think this problem generates a lot of self-confusion, but I think I've got an answer.

How about try this? (And tell me if you think there's something wrong)

"You can only answer false to this statement."

NOTE:The problem with statements asserting that the UTM is falliable is that it will tell you it can answer everything truthfully but you still havent found a way to show its lying since your intial statement was just an assumption, not the truth.

Title: Re: Universal Truth Machine
Post by tim on Aug 14^th, 2002, 3:48am

Mongolian_Beef: How do you know that the purported UTM is going to answer "false"? It might answer "true", thus failing to satisfy the conditions of the problem.

Title: Re: Universal Truth Machine
Post by Mongolian_Beef on Aug 14^th, 2002, 1:34pm

"You can only answer false to this statement."

tim: The fact is that the machine can always answer true, false, or undecided to any arbitrary question. Thus it will give the answer false.

However, you know that the machine always tells the truth so it must answer false since it can offer any of the above answers. in other words, you outsmart the machine because you know how it works.

it answers false when the answer is true because the machine always tells the truth although it could offer any of those three answers so it MUST answer false thus satsifying the conditions.

Title: Re: Universal Truth Machine
Post by tim on Aug 14^th, 2002, 8:06pm

No. You've actually got yourself into a contradiction here.

You start by assuming that the machine always tells the truth, and conclude that it doesn't. This does show that the machine can't always tell the truth value of an arbitrary statement, but the problem specifically asks for a true statement to which the machine will say false.

You've just proved that the machine doesn't work, so how can you assume that it does when proving that your statement satisfies the conditions of the problem!?

The fact is that you don't know how the machine works. You only know how the inventor claims that it works.

Title: Re: Universal Truth Machine
Post by anshil on Aug 16^th, 2002, 7:30am

There! I can operate google! This is a classical from goedel, esher, bach.

1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

Title: Re: Universal Truth Machine
Post by littlewing on Sep 6^th, 2002, 2:46am

The statement we should give the UTM is "You will answer False or Undecidable to this Statement".

the UTM can have 3 responses :
1) True - makes the statement true. and since the UTM did not give the ans as false or Undecidable , it is lying.
2) False , Undecidable - makes the statement true. hence UTM should have answered true.

In both cases , the Statement is TRUE.

The problem with "You can only answer false to this statement." is that the UTM can say Undecidable.

Title: Re: Universal Truth Machine
Post by zarathustra on Sep 8^th, 2002, 11:02pm

I understand that there is a problem that the universal truth machine is impossible if it simply prints out true, false, or undecidable. But how about if it was a little more intelligent? How about it prints out true, false, or if there is some sort of paradox involved then it explained exactly what the problem is and why it would never be able to give a correct result. I wonder if there would still be a way to foul it up...

Title: Re: Universal Truth Machine
Post by --- on Jan 15^th, 2003, 2:55pm

"this sentence is true only if it is false or undecidable but not if it's true"

the other way around.

Title: Re: Universal Truth Machine
Post by AaronSw on Nov 17^th, 2003, 4:03pm

This problem is impossible. My UTM can always return "true", and it will never violate the requirement of the solution (which requires saying something is <em>false</em>).

Title: Re: Universal Truth Machine
Post by Icarus on Nov 17^th, 2003, 5:15pm

It's true that this will technically make the current form of the problem unsolvable, (tim makes the same point on August 8, 2002) but I think I could disprove your claim that it is a UTM fairly easily anyway! :D

Perhaps the wording should be changed to "Someone has made a seemingly credible claim to have invented ...".

A UTM that always answers 'true' is not even slightly credible.

Title: Re: Universal Truth Machine
Post by Patashu on Sep 1^st, 2004, 3:14am

on 09/08/02 at 23:02:06, zarathustra wrote:

Easy.

Tell the UTM: "You will answer this statement with something besides true."

If it says true, then it's proven the statement false.
If it says false, then it's proven the statement true.
If it says undecided, then it's proven the statement true, thus it is decided.
If it explains the paradox, it's proven the statement true besides realizing how it works. It can't win! (unless I missed something)

Title: Re: Universal Truth Machine
Post by BNC on Sep 1^st, 2004, 6:13am

on 09/01/04 at 03:14:51, Patashu wrote:

You: "You will answer this statement with something besides true."

UTM: "That's right, Sir. I have just answered with something besides 'true'. "

Title: Re: Universal Truth Machine
Post by rmsgrey on Sep 1^st, 2004, 2:53pm

"Your response to this statement will not indicate it to be true"

Title: Re: Universal Truth Machine
Post by BNC on Sep 1^st, 2004, 3:46pm

Anyway, the way I see it, it's a clear "undecidable".

Title: Re: Universal Truth Machine
Post by rmsgrey on Sep 2^nd, 2004, 6:29am

The fun comes from the fact that, while the UTM cannot answer the statement correctly, any other person can.

Title: Re: Universal Truth Machine
Post by jonderry on Sep 13^th, 2004, 5:06pm

I see how it is possible to devise a proposition that the UTM will not be able to correctly solve, however I don't see how to ensure that the proposition is true; suppose there were such a proposition, then the UTM could simply repond "true" unless that made the claim false (in which case the proposition was not necessarily true).

Am I missing something?

Title: Re: Universal Truth Machine
Post by andrewcc32459 on Jun 11^th, 2005, 6:06pm

Ask it "Will the Universal Truth Machine say that the answer to this question is false?"

It cant say true because then the answer would be false

It cant say undecidable because then the answer would be false

Title: Re: Universal Truth Machine
Post by slapee on Nov 27^th, 2005, 8:16pm

how about asking the UTF a question that can be interpreted more than one way (e.g "0^0 = 0". this can either be true or false depending on how you look at it, since 0 times anything = 0, but anything^0 = 1.) ? would this work, or does the statement have to be boring and have only one interpretation?

Title: Re: Universal Truth Machine
Post by Icarus on Nov 28^th, 2005, 7:35pm

It would answer that one with "0^0 = 1", since that is the definition. It is far more useful to define 0^0 = 1 than it is to define it to be 0, or to leave it undefined, so the decision was made long ago to choose 1 as its value. This definition is universally accepted.

The fact that 0 times anything = 0 does not enter into this, since 0^0 does not involve multiplying 0 by anything. (The rule that 0 raised to any power is 0 is false. The correct rule is "0 raised to any power other than 0 is 0".)