You are either not logged in or not registered with our community. Click here to register.
 
December 03, 2016, 12:51:24 AM

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

Click here if you are having problems.
Default Wide Screen Beige Lilac Rainbow Black & Blue October Send us your theme!

Hark!  The Herald!
Holiday Issue 2016

Wiki Blogs Dicebot

Author Topic: Turing Complete - huh?  (Read 2660 times)

0 Members and 1 Guest are viewing this topic.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #50 on: November 06, 2012, 06:32:48 PM »
Bah.  I get your proof, Vekseid:

*snip spoiler*

To be honest I think you'll find it more productive to get some basic programming instruction, and begin from there. I don't think focusing on something being a Turing machine or not is conducive to understanding.

Seeing functions work, in process, and understanding how they get put together, call each other, etc. will give you a much clearer picture.

Quote
I thought it would be possible to, I dunno, "reverse engineer" I guess stormwyrm's argument from that but if it is its way beyond me.  I have like four A4 sheets full of random jottings and am getting nowhere.

We can reduce it like so.

DTM(x) = UTM(x) + 1
If UTM(x) can actually return.

So:

DTM(DTM) = UTM(DTM) + 1

And this is fine. There is no paradox. You've just put a wrapper around UTM. In order to clearly show a paradox, you have to take advantage of where DTM returns a zero, and construct a situation in which returning zero or an output must both be valid and invalid responses at the same time. Which is what you attempted to show.

For extra credit, why is my proof passing string descriptions rather than the function itself?

I always enjoy talking math - so it was mutually enjoyable :-)

Learning is at its most fun when it's consensual. >_>



Online stormwyrm

Re: Turing Complete - huh?
« Reply #51 on: November 06, 2012, 09:42:13 PM »
Well, the point of the machine that I have been calling the DTM is that the fact that trying to put it through a UTM produces a contradiction, shows that it cannot possibly be a Turing machine. It cannot be simulated by a UTM without running into a contradiction. It isn't a fully rigorous proof that what I have called the HTM cannot exist, but I think that given the fact that when one combines Turing machines together one still has a Turing machine, and that the UTM is definitely a Turing machine (much of Alan Turing's original 1936 paper is devoted to the logical description and construction of a universal Turing machine), how is it then possible to combine the UTM and HTM to produce something that is not a Turing machine? The only conclusion then, is that the HTM, which is what we have assumed to exist, is not itself a Turing machine.

The fact that you can combine the HTM with other Turing machines to produce something that looks like it can be simulated by a UTM is irrelevant: the fact that there is a way to combine it with other machines to produce something that can't be simulated in that way is the entire point of the admittedly non-rigorous proof.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #52 on: November 06, 2012, 10:17:20 PM »
Right, but your example didn't show that. You simply focused on the +1 artifact. That's not relevant to creating a contradiction.

To show the paradox, you need to essentially force a bug where your DTM must evaluate itself in such a way that it must return both or neither the program output+1 or false. The +1 is extraneous even in this scenario.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #53 on: November 06, 2012, 10:53:27 PM »
Well, riddle me this: what is the output of the DTM when you give its description to a UTM, with its description also on the tape with it?

From the definition of the UTM: UTM(d(DTM), d(DTM)) should produce DTM(d(DTM)).

Then, from the definition of the DTM in terms of the HTM, the HTM(d(DTM)) must be 1, because it halts for all possible inputs.

From our definition of the DTM, because HTM(d(DTM)) is one, DTM(d(DTM)) must then become UTM(d(DTM), d(DTM)) + 1.

So what will happen? Will we produce DTM(d(DTM)) or DTM(d(DTM)) + 1?

Offline Vekseid

Re: Turing Complete - huh?
« Reply #54 on: November 06, 2012, 11:05:16 PM »
Well, riddle me this: what is the output of the DTM when you give its description to a UTM, with its description also on the tape with it?

From the definition of the UTM: UTM(d(DTM), d(DTM)) should produce DTM(d(DTM)).

UTM(e(DTM(d(DTM))) will equal DTM(d(DTM)), as expected.

We must compare functional equivalences, remember.

UTM(d(DTM)) will equal DTM(d(DTM)) + 1

Quote
Then, from the definition of the DTM in terms of the HTM, the HTM(d(DTM)) must be 1, because it halts for all possible inputs.

This is fine.

Quote
From our definition of the DTM, because HTM(d(DTM)) is one, DTM(d(DTM)) must then become UTM(d(DTM), d(DTM)) + 1.

So what will happen? Will we produce DTM(d(DTM)) or DTM(d(DTM)) + 1?

As I wrote above, throw out everything regarding the HTM portion. Replace DTM with ATM, where ATM is a normal TM that adds a 1 at the end of every output after halting.

If you actually caused a paradox here, you would show that the ATM causes a paradox.
It's trivial to show that the ATM is possible.

Instead, you're just taking on a potentially ever-longer chain of +1s as you emulate the behavior.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #55 on: November 07, 2012, 12:24:26 AM »
ctually caused a paradox here, you would show that the ATM causes a paradox.
It's trivial to show that the ATM is possible.

Instead, you're just taking on a potentially ever-longer chain of +1s as you emulate the behavior.

And with that, you have just stated that there exists an input to the DTM, namely its own description, for which DTM doesn't halt. But didn't we just say that by definition the DTM should halt for all inputs, because of the way we used the HTM? If you say that it doesn't halt, then your HTM is producing wrong results, and it doesn't really settle the halting problem. If you say it does halt, then why, when we give its description to a UTM, does it keep adding 1's when we simulate it?

It's Epimenides the Cretan saying all Cretans are liars. Or that story of Nasrudin:

There was a king who wanted all his subjects to tell the truth, so he set up a gallows in his city where anyone who did not speak the truth was to be hanged. Nasrudin came to the city, and a guard there asked: "Where are you going? Tell the truth, if you do not you shall be hanged on that gallows."

"I am going to be hanged on that gallows," Nasrudin replied.

"I don't believe you!" said the guard.

"Then hang me!" answered Nasrudin.

"But that would make it the truth!"

"Exactly," said Nasrudin. "Your truth."

EDIT: actually, Vekseid, you got me to stating the true nature of the paradox inherent in the DTM properly, which I have failed to do so properly before. I've been AWOL from graduate school for too long XD
« Last Edit: November 07, 2012, 12:33:45 AM by stormwyrm »

Offline Vekseid

Re: Turing Complete - huh?
« Reply #56 on: November 07, 2012, 12:52:50 AM »
And with that, you have just stated that there exists an input to the DTM, namely its own description, for which DTM doesn't halt. But didn't we just say that by definition the DTM should halt for all inputs, because of the way we used the HTM? If you say that it doesn't halt, then your HTM is producing wrong results, and it doesn't really settle the halting problem. If you say it does halt, then why, when we give its description to a UTM, does it keep adding 1's when we simulate it?

Hmm?

Same thing occurs with the ATM, thus the problem with your description. And it's still halting, it's just that we get the additional +1s as we nest ATM/DTM descriptions of themselves.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #57 on: November 07, 2012, 01:26:12 AM »
I think I have gotten somewhat confused here. So let's start again from the beginning.

d(TM) - the description of a Turing machine TM.
UTM(e, x) - The universal Turing machine. Given a description of a Turing machine e and the tape contents x, perform a simulation of the Turing machine corresponding to the description e.
HTM(e) - the halting problem decider. Given a description of a Turing machine e, return 1 if the Turing machine described by e halts for all possible inputs, or return 0 if there exists some input to that machine that will make it run forever.
DTM(e) - if HTM(e) is 1, then UTM(e, e) and print an extra 1 at the end of the tape when the UTM simulation stops. Otherwise, just print 0 on the tape.

We note the following things:

1. From the way we defined the DTM, HTM(d(DTM)) clearly should be 1, so there should be no possible input to DTM that will cause it to run forever.

2. What happens though, when we give it the input d(DTM)? It attempts to do UTM(d(DTM), d(DTM)) again, adding a 1 to the tape, again, and again, and again, forever.

3. So, in that case, can you really still say that HTM(d(DTM)) is 1? Maybe it's really zero. If it's zero then, well, the machine halts, just printing a zero on its tape! So what is it, really?

Offline Vekseid

Re: Turing Complete - huh?
« Reply #58 on: November 07, 2012, 01:32:38 AM »
2. What happens though, when we give it the input d(DTM)? It attempts to do UTM(d(DTM), d(DTM)) again, adding a 1 to the tape, again, and again, and again, forever.

No, it only adds 1 once. But it does add it, exactly once.

Replace DTM with my ATM and you'll get the same deal.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #59 on: November 07, 2012, 01:54:54 AM »
No, it only adds 1 once. But it does add it, exactly once.

Replace DTM with my ATM and you'll get the same deal.

However, attempts to evaluate UTM(d(DTM), d(DTM)) before doing that, which is of course DTM(d(DTM)), and the cycle goes around again and again and again, running forever. So what then is the real value of HTM(d(DTM))? 1? That can't be right, because it puts itself in an infinite loop! 0? Then, well, we take the else branch of our if, and halt, after printing 0, so that can't be right either.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #60 on: November 07, 2012, 02:29:02 AM »
Where are you forcing the cycle to continue? That would be a valid and possibly novel example of the paradox if you forced that.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #61 on: November 07, 2012, 06:13:40 AM »
Where are you forcing the cycle to continue? That would be a valid and possibly novel example of the paradox if you forced that.

Recall the definition of DTM:

DTM(e): if HTM(e) is 1
                  UTM(e, e) + 1
                else
                   0

and recall that UTM(e, x) is a universal Turing machine that takes the Turing machine description e and interprets it, using x as the contents of the input tape. It basically says that we should create a new "interpreter instance" as it were and simulate the Turing machine described by e with x as its input tape. So UTM(d(DTM), d(DTM)) is the same as starting up a new DTM(d(DTM)) all over again.

So when we get d(DTM) and pass it to DTM itself, i.e. attempt to evaluate DTM(d(DTM)), either of these two things is true:

1. DTM terminates for all possible inputs, i.e. HTM(d(DTM)) is 1, or
2. There exists some input to DTM that will cause it to run forever, i.e. HTM(d(DTM)) is 0.

Assuming HTM(d(DTM)) is 1, then we take the 'if' branch, and which then contains UTM(d(DTM), d(DTM)), which is the same as saying DTM(d(DTM)), leading us back to where we started, It then does not terminate, so HTM(d(DTM)) is not 1. But assuming the opposite, that HTM(d(DTM)) is 0, means we take the 'else' branch, and we terminate printing 0. The DTM essentially behaves just like that smartass Nasrudin in the story.

So then, what are our options, and what does this mean for the theory of computation? We can say that either HTM(d(DTM)) is 0 or 1, meaning that we are saying something obviously false, or we can say that HTM(e) is not a Turing machine and cannot be simulated by one, thus it has no Turing machine description, and any composite machine incorporating it cannot have one either.
« Last Edit: November 07, 2012, 06:23:22 AM by stormwyrm »

Offline Vekseid

Re: Turing Complete - huh?
« Reply #62 on: November 07, 2012, 07:01:42 AM »
Thing is you've never put in any description why it magically decides to start up again.

If we assume that DTM(d(DTM)) halts (a prerequisite for your argument), then UTM(d(DTM), d(DTM)) simply runs the magic emulator through its own description, and stops.

Basically from the functional sense you're never actually trapping the false value anywhere at all.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #63 on: November 07, 2012, 07:48:34 AM »
Thing is you've never put in any description why it magically decides to start up again.

The description of why it magically decides to start up again is precisely what the UTM operator we have here does. The UTM operator is essentially the equivalent of the eval function in the languages that have it (e.g. Lisp, Scheme, Perl, Python, Ruby, etc.), in that it will spawn a new interpreter instance and interpret the description of whatever was passed to it. I don't see why this is so hard to accept. It is the nature of what a universal Turing machine does!

If we assume that DTM(d(DTM)) halts (a prerequisite for your argument), then UTM(d(DTM), d(DTM)) simply runs the magic emulator through its own description, and stops.

But when it runs the magic emulator through its own description, it's forced to go back and run UTM(d(DTM), d(DTM)) (i.e. itself) again and again, and so run forever.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #64 on: November 07, 2012, 07:59:42 AM »
Hmm?

Evaluation of a program does not entail execution.
Edit: In the human sense of evaluation - analysis and such, not eval()

Even if it did, the result is well-formed - it just outputs zero.


Online stormwyrm

Re: Turing Complete - huh?
« Reply #65 on: November 07, 2012, 08:25:40 AM »
Hmm?

Evaluation of a program does not entail execution.
Edit: In the human sense of evaluation - analysis and such, not eval()

Well, that seems to be the source of the misunderstanding then. The verb 'evaluate' is frequently used in programming circles to denote getting the value produced by an expression (by executing the code corresponding to the expression) or returned from the execution of the program, and to many programmers 'evaluate' and 'execute' are synonymous in a programming context.

So to put it in a way that minimises confusion, UTM(e, x) executes the Turing machine described by e with x on its input tape.

Even if it did, the result is well-formed - it just outputs zero.

It outputs zero? Why? Is it because HTM(d(DTM)) was zero? If so, then what is the input to DTM that makes it run forever? d(DTM)? But you just said that giving it that value makes it output zero and hence terminate!

No, there is a real paradox here, and the only real way to resolve it is to say that HTM cannot be simulated by a Turing machine.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #66 on: November 07, 2012, 10:14:34 PM »
Well, that seems to be the source of the misunderstanding then. The verb 'evaluate' is frequently used in programming circles to denote getting the value produced by an expression (by executing the code corresponding to the expression) or returned from the execution of the program, and to many programmers 'evaluate' and 'execute' are synonymous in a programming context.

So to put it in a way that minimises confusion, UTM(e, x) executes the Turing machine described by e with x on its input tape.

And if it executes another simulation inside of it, it either exits normally, or runs forever, in which case there is no logical reason why UTM(d(DTM),d(DTM)) == DTM(d(DTM)) == 0

Quote
It outputs zero? Why? Is it because HTM(d(DTM)) was zero? If so, then what is the input to DTM that makes it run forever? d(DTM)? But you just said that giving it that value makes it output zero and hence terminate!

0 or 01, whatever. If there is a loop, it kills the loop and stops.

Online stormwyrm

Re: Turing Complete - huh?
« Reply #67 on: November 07, 2012, 11:48:58 PM »
And if it executes another simulation inside of it, it either exits normally, or runs forever, in which case there is no logical reason why UTM(d(DTM),d(DTM)) == DTM(d(DTM)) == 0

Well, if DTM(d(DTM)) runs forever, then well, that means that the HTM is actually unable to determine whether some Turing machine description actually runs for ever: it cannot really resolve the halting problem!, contradicting the way we defined it initially!

0 or 01, whatever. If there is a loop, it kills the loop and stops.

What kills the loop? Once UTM(d(DTM), d(DTM)) begins, it will run forever, putting the lie to HTM(d(DTM)) == 1.

Again riddle me this: what is HTM(d(DTM))? Think of your answer carefully.

Offline Vekseid

Re: Turing Complete - huh?
« Reply #68 on: November 07, 2012, 11:56:24 PM »
I honestly have no idea what you are trying to say, to be perfectly frank.