Author |
Topic: Universal Truth Machine (Read 8445 times) |
|
jkemp
Guest
|
"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.
|
| « Last Edit: Aug 8th, 2002, 5:01pm by william wu » |
 IP Logged |
|
|
|
bartleby
Guest
|
 |
Re: Universal Truth Machine
« Reply #1 on: Aug 8th, 2002, 9:49am » |
 Quote  Modify
 Remove
|
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" 
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender: 
Posts: 102
|
|
Re: Universal Truth Machine
« Reply #2 on: Aug 8th, 2002, 9:59am » |
Quote Modify
|
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.
|
|
IP Logged |
My arcade cabinet
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Universal Truth Machine
« Reply #3 on: Aug 8th, 2002, 12:08pm » |
Quote Modify
|
Technical quibble: Bartleby I think you mean undecidability or incompleteness. Any NP-complete problem is decidable and would be correctly answered by the UTM.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Universal Truth Machine
« Reply #4 on: Aug 8th, 2002, 1:24pm » |
Quote Modify
|
Jon,
How about, "does the first 0 of Chaitin's constant occur at an even index?"
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: Universal Truth Machine
« Reply #5 on: Aug 8th, 2002, 3:39pm » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Universal Truth Machine
« Reply #7 on: Aug 8th, 2002, 4:36pm » |
Quote Modify
|
on Aug 8th, 2002, 3:45pm, Jonathan_the_Red wrote:| "This statement is undecidable?" |
|
No, because that statement could correctly be considered false.
|
|
IP Logged |
|
|
|
jkemp
Guest
|
|
Re: Universal Truth Machine
« Reply #9 on: Aug 8th, 2002, 5:29pm » |
Quote Modify
Remove
|
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).
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Universal Truth Machine
« Reply #10 on: Aug 8th, 2002, 5:35pm » |
Quote Modify
|
on Aug 8th, 2002, 3:39pm, 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.
|
|
IP Logged |
|
|
|
jkemp
Guest
|
|
Re: Universal Truth Machine
« Reply #11 on: Aug 8th, 2002, 5:40pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Universal Truth Machine
« Reply #12 on: Aug 8th, 2002, 5:43pm » |
Quote Modify
|
on Aug 8th, 2002, 5:29pm, jkemp wrote: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). |
|
But "The UTM is fallible" an assumption, not the truth. Plus, you're also assuming the UTM has knowledge of its own fallibility.
|
|
IP Logged |
|
|
|
jkemp
Guest
|
|
Re: Universal Truth Machine
« Reply #13 on: Aug 8th, 2002, 5:48pm » |
Quote Modify
Remove
|
> 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).
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Universal Truth Machine
« Reply #14 on: Aug 8th, 2002, 5:51pm » |
Quote Modify
|
on Aug 8th, 2002, 5:48pm, 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.
|
| « Last Edit: Aug 8th, 2002, 5:51pm by Jeremiah Smith » |
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Universal Truth Machine
« Reply #15 on: Aug 8th, 2002, 7:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
anshil
Newbie
Posts: 41
|
|
Re: Universal Truth Machine
« Reply #16 on: Aug 8th, 2002, 9:59pm » |
Quote Modify
|
What is the answert to the ultimate question of life, universe and everything?
|
|
IP Logged |
|
|
|
Archon
Newbie
Gender:
Posts: 39
|
|
Re: Universal Truth Machine
« Reply #17 on: Aug 9th, 2002, 7:22am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Mongolian_Beef
Newbie
Posts: 11
|
|
Re: Universal Truth Machine
« Reply #18 on: Aug 13th, 2002, 10:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Universal Truth Machine
« Reply #19 on: Aug 14th, 2002, 3:48am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Mongolian_Beef
Newbie
Posts: 11
|
|
Re: Universal Truth Machine
« Reply #20 on: Aug 14th, 2002, 1:34pm » |
Quote Modify
|
"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.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Universal Truth Machine
« Reply #21 on: Aug 14th, 2002, 8:06pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
anshil
Newbie
Posts: 41
|
|
Re: Universal Truth Machine
« Reply #22 on: Aug 16th, 2002, 7:30am » |
Quote Modify
|
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."
|
|
IP Logged |
|
|
|
littlewing
Newbie
Posts: 1
|
|
Re: Universal Truth Machine
« Reply #23 on: Sep 6th, 2002, 2:46am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
zarathustra
Newbie
Posts: 7
|
|
Re: Universal Truth Machine
« Reply #24 on: Sep 8th, 2002, 11:02pm » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print