Topic: Turing Complete - huh?

[Kythia]

So presumably a perceptron can't do that because it has only one input and it takes two inputs to determine an XOR situation?

Sorry.  Please do feel free to ignore me.

[Oniya]

Right.  The XOR has to know that one and only one input is 'on'.

[Vekseid]

Yeah, be warned.  I'm relatively certain I've driven people to suicide with incessant questioning.  Fair warning.

But, since you said.

I'm struggling to reconcile both your and Oniya's examples for XOR.  I've just, literally, been playing with my stair lights and if both are off then the light is off.  However, if one of them is on then the light is on.  Turning the other on doesn't affect the light.  But it seems from Vekseid's that it should only work if only one of them is on - so flicking both on should, I dunno, turn it off?  I've obviously misunderstood one or both examples somewhere.

You have a different sort of switch than Oniya was expecting, as described. Your switches are an example of an OR operation. If your house was wired such that, when both were up, or both were down, your light was off, but otherwise on, that would be XOR.

As to the rest, am I understanding right in that:
1) My simplification was an over-simplification
2) The key point being that some machines have a capability to give up or otherwise interrupt an infinite loop

The halting problem is just the best 'example' of an undecidable problem, because it represents a general case of undecidable problems.

'General' has an important meaning here. "All possible examples of." You cannot catch every infinite loop. What you can do, however, is structure your program such that it permits no infinite loops. This makes it necessarily less powerful - you are beginning from the start with saying "I will only solve these problems in this way." Our program is incomplete - it cannot do all things that can be done, it isn't even 'Turing Complete', but this is not a necessary condition for a useful program. You can make a simple calculator 'bug free' (for a rather strict sense of bug free and simple, but still), and still find it highly useful. But there will be things that you might want to try with it that you won't be able to do.

And that while I can't, or "one" can't rather - the issue being that its not my mathematical ineptitude thats at fault here - check whether or not a statement is provable (meaning "doesn't enter a infinite loop" in this sense) a Turing Complete system can prove anything that's provable?

You're harder on yourself than you need to be. : )

And yes, but knowing in advance what is provable and what isn't is the problem.

An easy example is the twin prime conjecture. This may actually be an unsolvable problem. We don't know if it's provable or not. A Zeno Machine - a Turing machine capable of completing an infinite number of steps in a finite amount of time - could 'prove' this by simply finding all twin primes and seeing if the result is infinite or not.

But we mortals have no such luxury. All we can do is deploy ridiculous amounts of computing power at the problem to come up with ever-larger twins for pure giggles. Can have a computer try to find them, and it might run forever, or it might not. This, and problems like it, are what the Halting problem refers to.

And of course, we could run this operation run inside some context that starts poking. "Uhh, this is taking a REALLY long time, should we stop now?" - We thus give up on the possibility of solving the problem, admitting to being incomplete, but giving us a scenario where we do in fact halt.

So presumably a perceptron can't do that because it has only one input and it takes two inputs to determine an XOR situation?

It's more appropriate to say that a perceptron network tests whether or not some set of inputs crosses a threshold. A single layer that triggers on one true input must therefore trigger on multiple true inputs, whereas a XOR turns off once another threshold is crossed. A single-layer network cannot do the latter.

Sorry.  Please do feel free to ignore me.

Don't apologize. : /

However, if you want more details on perceptrons and neural networks, it's best to make a new thread about them. It's not difficult to explain, just don't want to run off on an AI tangent.

[Kythia]

The halting problem is just the best 'example' of an undecidable problem, because it represents a general case of undecidable problems.

'General' has an important meaning here. "All possible examples of." You cannot catch every infinite loop. What you can do, however, is structure your program such that it permits no infinite loops. This makes it necessarily less powerful - you are beginning from the start with saying "I will only solve these problems in this way." Our program is incomplete - it cannot do all things that can be done, it isn't even 'Turing Complete', but this is not a necessary condition for a useful program. You can make a simple calculator 'bug free' (for a rather strict sense of bug free and simple, but still), and still find it highly useful. But there will be things that you might want to try with it that you won't be able to do.

That makes sense.  I'm saying "My program can't deal wuth an infinite loop but fortunately I can write a program that does everything I want from it and cannot possibly, in the strictest sense possible, enter an infinite loop.

You're harder on yourself than you need to be. : )

I'm actually not.  I'm awesome at any number of things, maths isn't one of them.  I know how much change to expect from a shop, like, I'm not saying I have bad enough maths for it to intefere with my life.  But I'm pretty OK with knowing there are some mathematical actions that I just can't do.  I'll live.

And yes, but knowing in advance what is provable and what isn't is the problem.

An easy example is the twin prime conjecture. This may actually be an unsolvable problem. We don't know if it's provable or not. A Zeno Machine - a Turing machine capable of completing an infinite number of steps in a finite amount of time - could 'prove' this by simply finding all twin primes and seeing if the result is infinite or not.

But we mortals have no such luxury. All we can do is deploy ridiculous amounts of computing power at the problem to come up with ever-larger twins for pure giggles. Can have a computer try to find them, and it might run forever, or it might not. This, and problems like it, are what the Halting problem refers to.

And of course, we could run this operation run inside some context that starts poking. "Uhh, this is taking a REALLY long time, should we stop now?" - We thus give up on the possibility of solving the problem, admitting to being incomplete, but giving us a scenario where we do in fact halt.

Gotcha.  So we're artificially halting the problem after, say ten minutes and sayign "Welp, thats long enough" and thus not actually coming to a full and, you know, rigorous conclusion on whether the problem would eventually be solved or not.

It's more appropriate to say that a perceptron network tests whether or not some set of inputs crosses a threshold. A single layer that triggers on one true input must therefore trigger on multiple true inputs, whereas a XOR turns off once another threshold is crossed. A single-layer network cannot do the latter.

Don't apologize. : /

However, if you want more details on perceptrons and neural networks, it's best to make a new thread about them. It's not difficult to explain, just don't want to run off on an AI tangent.

Ah see here we're running in to a problem that I actually run in to a lot.  It's easy for you to say (or at least it seems easy for you to say) "well, thats more of an AI discussion and is off topic".  My issue is that I'm in uncharted lands here and don't know where the map lines are.  I don't have enough knowledge of the categories and sub-divisions of the subject area to necessarily know when I've gone off topic and am exploring some peripherally relevant tangent and when it's core stuff, intrinsic to the topic at hand.

Not that I'm ridiculing or otherwise ignoring your suggestion.  Simply saying that as I'm running with a map, its easy to go up an intersting looking side ally without realising what I've done.

[Vekseid]

That makes sense.  I'm saying "My program can't deal wuth an infinite loop but fortunately I can write a program that does everything I want from it and cannot possibly, in the strictest sense possible, enter an infinite loop.

'Easier said than done' caveats of course apply.

There are also blocking problems called deadlocks where program A has resource X and needs resource Y to give it up, but program B has locked up resource Y and can't release it until it has resource X. Until recently this has been the usual cause of programs hanging indefinitely, rather than an infinite loop per se. Over the past decade or so there has been a lot of effort spent on making various software services non-blocking, and this has drastically changed the limits of what is possible. Facebook, Twitter, even Elliquiy would not be possible (at least on our current hardware) without this little revolution.

Again, there's a tradeoff, particularly in terms of how certain you can be about the 'state' of things at an exact moment. But this is almost pedantic - do you care if you got your friend's message at 12:01:42.935 PM versus 12:01:42.906 PM? I know some people are REALLY impatient, but still...

In E's case, because the implementation for the current software is somewhat poor, this shows up in the form of e.g. telling you you have an unread message for longer than it ought to, as a more blatant example that has the same cause. It's still a bug, however, in the sense that it is certainly possible to do better.

I'm actually not.  I'm awesome at any number of things, maths isn't one of them.  I know how much change to expect from a shop, like, I'm not saying I have bad enough maths for it to intefere with my life.  But I'm pretty OK with knowing there are some mathematical actions that I just can't do.  I'll live.

We all have a finite amount of resources to devote to problems that face us. There's nothing to be ashamed of regarding stating "Alright, I'll let the rest of the world handle that. My contribution will be this, instead." I realize I'm a nerd, but problems like the twin prime conjecture don't keep me up at night. Have plenty of other issues to solve. : )

Gotcha.  So we're artificially halting the problem after, say ten minutes and sayign "Welp, thats long enough" and thus not actually coming to a full and, you know, rigorous conclusion on whether the problem would eventually be solved or not.

Correct.

Ah see here we're running in to a problem that I actually run in to a lot.  It's easy for you to say (or at least it seems easy for you to say) "well, thats more of an AI discussion and is off topic".  My issue is that I'm in uncharted lands here and don't know where the map lines are.  I don't have enough knowledge of the categories and sub-divisions of the subject area to necessarily know when I've gone off topic and am exploring some peripherally relevant tangent and when it's core stuff, intrinsic to the topic at hand.

Not that I'm ridiculing or otherwise ignoring your suggestion.  Simply saying that as I'm running with a map, its easy to go up an intersting looking side ally without realising what I've done.

Well I mean, presenting a perceptron network as a threshold test suffices for its role in this topic. Quite literally, every single neuron in your brain takes a number of inputs (from a thousand to a hundred thousand, as a human), and if the 'weight' provided by these inputs crosses a certain point, then that neuron fires.

But that's all it can do. That one neuron can't say "Well, if it gets too high, I won't fire." Instead, what needs to be done, is have another neuron with a separate set of weights from the same input, where it fires if it goes below a certain threshold, but does not fire above.

So you add a third neuron that takes its input from the previous two, making it a second layer. It fires when both of the first layer neurons fire. Now you have your XOR. : )

Beyond this, though, neural networks are a huge segment of AI, and AI is itself a huge segment of computer science. Can certainly go into it, but the vast majority of its scope is going to be outside of this thread.

[stormwyrm]

Let's be a bit more precise about the statement of the halting problem then. You remember the idea of a universal Turing machine (UTM) right? It's a Turing machine, which, when given the description of some other Turing machine, i.e. the states it has, the symbols it uses, the rules for transitioning between states, is capable of simulating the behaviour of that Turing machine. Essentially, it's the idea behind the modern stored-program computer. The halting problem states that it is impossible to build a Turing machine that, given the description of some Turing machine suitable for use by a UTM, is capable of deciding whether or not that machine will ever stop processing.

Basically, one can think of a UTM as a machine that accepts the description of an arbitrary TM and the input to the tape of that TM, writes the output of the simulated TM on its tape. Say we had some hypothetical Turing machine (let's call this the HTM) capable of settling the halting problem, i.e. a Turing machine which, when given the description of any arbitrary TM, writes a 1 on its tape if the described TM will stop processing after a finite time no matter what input is given to its tape, or 0 if it might run forever for some inputs on its tape. We can then combine the UTM with the HTM into another Turing machine (call this the DTM) that, when given the description of some TM, will do the following: if the halting problem TM produces 1, apply the UTM to the same description, with the description itself also as input, and add an extra 1 to the end of the output when the simulation stops. If the halting problem TM produces 0, then just write a 0 on the tape. Now, the DTM should also have its own description, since it is also supposed to be a Turing machine, and this is where shit starts to hit the fan really bad. Clearly, from the way we built it up, the DTM will eventually stop no matter what input we give it, so the result of giving its description to the HTM should be 1. Now, what happens when we feed the DTM's description to our UTM, with its own description as input? Well, clearly, that's just the result of the DTM run with its own description as input. But wait! Since the HTM produces 1 for the DTM's description, shouldn't the simulation instead produce the result of the DTM with an extra 1 attached to the end from the way we defined it? So what is it, really?! We have a contradiction here, and the only logical conclusion we can draw is that the existence of the HTM is a logical impossibility.

It's a classic reductio ad absurdum proof, similar to Georg Cantor's celebrated diagonal argument.

You may find this Wikipedia article pertinent:

https://en.wikipedia.org/wiki/Description_number

[Kythia]

OK, that took a lot of reading so apologies if this is wrong - if so the flaw is probably on my end.  But...

Doesn't that disproof only work because you've specified an extra one on the end of the output?  Does it not disappear if:

The HTM outputs "1" if a problem will halt, "0" otherwise.
The DTM takes as input a TM.  It first runs it through the HTM.  If the HTM output is 1, then it processes as normal, else it writes 0
So.  Feeding the DTM into the HTM will, as you say, produce 1.  It will definately stop.
That means, like you say, that our DTM can, in the case of being having a DTM as input, essentially ignore the HTM. 
So feeding the DTM into the DTM ignores the HTM and just returns whatever its normal output would be.

What am I missing here?  Even I don't have the sort of psychopathic self assurance to claim I've solved a problem that has been plaguing mankind for half a century with twenty minutes thought, but I don't see what I've missed.

[stormwyrm]

OK, that took a lot of reading so apologies if this is wrong - if so the flaw is probably on my end.  But...

Doesn't that disproof only work because you've specified an extra one on the end of the output?  Does it not disappear if:

The HTM outputs "1" if a problem will halt, "0" otherwise.
The DTM takes as input a TM.  It first runs it through the HTM.  If the HTM output is 1, then it processes as normal, else it writes 0
So.  Feeding the DTM into the HTM will, as you say, produce 1.  It will definately stop.
That means, like you say, that our DTM can, in the case of being having a DTM as input, essentially ignore the HTM. 
So feeding the DTM into the DTM ignores the HTM and just returns whatever its normal output would be.

What am I missing here?  Even I don't have the sort of psychopathic self assurance to claim I've solved a problem that has been plaguing mankind for half a century with twenty minutes thought, but I don't see what I've missed.

We have three machines here:

The UTM (universal Turing machine) - takes as input the description of a Turing machine, and the input tape that is to be fed to the input Turing machine. This will simulate the behaviour of the described Turing machine.

The HTM (halting problem Turing machine) - the hypothetical Turing machine that can solve the halting problem. Given the description of a Turing machine, it prints 1 on the tape if the Turing machine will halt for all possible inputs, or 0 if there exists some sequence of inputs to the described Turing machine that will cause it to run forever.

The DTM (diagonal Turing machine) - A clever combination of the UTM and the HTM. Just as with the UTM, takes as input the description of a Turing machine and the input tape that is to be fed to the input Turing machine. First thing it does is use the HTM on the description. If the HTM produces a 1, then it will run the UTM on the description and input tape that were its original inputs, but it will print a 1 after the last symbol produced by the UTM simulation (which will eventually finish because the HTM assures us of this). If the HTM produces a 0, it will just print a 0.

Now, the question becomes: what happens when you pass the description of the DTM to a universal Turing machine, with the DTM's description as the contents of the input tape? By our definition of the UTM, it will simulate the behaviour of the DTM with its own description. But will that have an extra 1 appended or not? Therein lies the contradiction. It is easier to express in symbols:

description of TM = d(TM)
UTM(d(DTM), d(DTM)) = DTM(d(DTM), d(DTM))
HTM(d(DTM)) = 1

but, we have defined DTM(e, x) to be:

DTM(e, x) -> if HTM(e) is 1
                           UTM(e, x) + 1
                        else
                            0
                        end

so DTM(d(DTM), d(DTM)) == DTM(d(DTM), d(DTM)) + 1 That is obviously a contradiction.

[Kythia]

Sorry, phrased that badly.

I get that, my problem is why the one is being appended?  The disproof seems (and here I'm likely wrong) to only work if the DTM appends an extra 1, but goddamnit we built the DTM - why don't we just build it so it doesn't append the extra 1.  Is that in any way necessary?

Using your symbols - and I'm not sure I've understood the notation correctly:

----------------

description of TM = d(TM)
UTM(d(DTM), d(DTM)) = DTM(d(DTM), d(DTM))
HTM(d(DTM)) = 1

but, we have defined DTM(e, x) to be:

DTM(e, x) -> if HTM(e) is 1
                          UTM(e, x)
                        else
                            0
                        end

so DTM(d(DTM), d(DTM)) == DTM(d(DTM), d(DTM))

(my changes bolded)
Which is trivially true.

------------

Or to phrase it another way - is problem here that there is no way of creating a DTM which doesn't append a one, because it seems like the only reason there is any contradiction is because we're insisting on the DTM doing so.

[Moraline]

I've been following this for the last couple of pages. Great discussion by the way.

My question is going back to the original post then.

How exactly do you differentiate between a Turing Complete and a Non-Turing complete programming language then?

Isn't the simplest explanation that any program that can contain an infinite loop as per the instructions that the programming language is built around would be a Turing Complete program and any program that can't contain a loop be Non-Turing complete?

Since programming languages such as Fortran, Java and C+ all contain such code, they are Turing Complete.
Whereas basic HTML is Non-Turning Complete because it is incapable of creating a loop (the instructions end when the last line of code is read, whether a result it returned or not.)


As for all the talk about Turning Machines, a Turing Machine is an impossibility because it calculates to an infinite number of probabilities. For the machine to answer the question we need to add another variable or more accurately another dimension of time to the calculation which breaks the probability of the Turing Machines existence (and that goes down a whole other rabbit hole.)

Which is why the human brain or any AI machine has to have some other variable(or dimension) to the Turing Complete programming to arrive at an answer. It also explains why the human brain responds in certain ways to illusions and riddles - our wonderful Turing Complete brains have predetermined (or learned) points where we turn off the infinite loop of calculations and arrive at an answer/decision.

[Vekseid]

I've been following this for the last couple of pages. Great discussion by the way.

My question is going back to the original post then.

How exactly do you differentiate between a Turing Complete and a Non-Turing complete programming language then?

For practical purposes, a Turing complete language is a language with the capacity to modify its own program state in an arbitrary fashion. You can construct exceptions (e.g. if you somehow did this without a data store), but the only major non-Turing complete language that comes to mind is SQL sans procedures (as is the case with any major website actually using SQL). This is just offhand. I'm sure there are others.

In SQL, the state is supposed to be the database itself. It's a language (structured query language) even, but without procedures your script consists of a bunch of lines that typically are only executed once, as atomic statements, you don't bounce back and forth between them as in a normal language, if that makes sense.

Isn't the simplest explanation that any program that can contain an infinite loop as per the instructions that the programming language is built around would be a Turing Complete program and any program that can't contain a loop be Non-Turing complete?

A programming language that has no capacity to store information can easily create an infinite loop. A language that only understood the while (1) { continue; } construct, for example.

A Turing Complete language must permit undecidable operations (such as exposed by the halting problem), but other languages might run into such situations.

Since programming languages such as Fortran, Java and C+ all contain such code, they are Turing Complete.
Whereas basic HTML is Non-Turning Complete because it is incapable of creating a loop (the instructions end when the last line of code is read, whether a result it returned or not.)

HTML is a markup language. It is not a programming language. Markup is nothing more than the return of illumination after Gutenburg killed it off with the printing press.

As for all the talk about Turning Machines, a Turing Machine is an impossibility because it calculates to an infinite number of probabilities. For the machine to answer the question we need to add another variable or more accurately another dimension of time to the calculation which breaks the probability of the Turing Machines existence (and that goes down a whole other rabbit hole.)

The lack of infinite space in which to perform computations is usually considered to be somewhat facetious, at least for most programming problems in the modern era. It's an ideal, but we have ways of space-bounding problems to compensate. Your new machine with a two terabyte hard drive is 'technically not' a Turing machine, but it's still capable of solving an obscene number of problems.

Which is why the human brain or any AI machine has to have some other variable(or dimension) to the Turing Complete programming to arrive at an answer.

I am not sure why you think so, but this is not the case.

It also explains why the human brain responds in certain ways to illusions and riddles - our wonderful Turing Complete brains have predetermined (or learned) points where we turn off the infinite loop of calculations and arrive at an answer/decision.

Our thought loop exists with a continuous assimilation of data being fed into it. We know rather little of it, but my guess would be that the brain is not subject to infinite loops because this continuous absorption diffuses 'loopish' thought processes, and have our own desire to seek out alternate stimuli if something is driving us nuts. Just a guess, I imagine we'll see a paper on it sometime in the next couple decades.

[Oniya]

Our thought loop exists with a continuous assimilation of data being fed into it. We know rather little of it, but my guess would be that the brain is not subject to infinite loops because this continuous absorption diffuses 'loopish' thought processes, and have our own desire to seek out alternate stimuli if something is driving us nuts. Just a guess, I imagine we'll see a paper on it sometime in the next couple decades.

Couldn't obsessive ideations be considered 'loopish'?  Or really, any compulsive behavior.  I've read descriptions of people who have extreme OCD to the point of 'infinite looping' (i.e., even though the 'input' should dictate otherwise, the 'process' doesn't go to an 'end state', like continuing to check the porch light after determining that it's off.) 

[Moraline]

Thanks for the answer, Veks. That more clearly defines for me how/what a Turing complete programming language is.

[Vekseid]

Couldn't obsessive ideations be considered 'loopish'?  Or really, any compulsive behavior.  I've read descriptions of people who have extreme OCD to the point of 'infinite looping' (i.e., even though the 'input' should dictate otherwise, the 'process' doesn't go to an 'end state', like continuing to check the porch light after determining that it's off.)

If they're able to continue on with their lives in some fashion, it's not infinite. Under my very loose, completely non-scientific hypothesis there, it would imply that someone under such self-hypnotic effects didn't absorb said prior sensory input. Pretty sure most of us have had that happen.

[stormwyrm]

Sorry, phrased that badly.

I get that, my problem is why the one is being appended?  The disproof seems (and here I'm likely wrong) to only work if the DTM appends an extra 1, but goddamnit we built the DTM - why don't we just build it so it doesn't append the extra 1.  Is that in any way necessary?

The extra 1 is the whole point of the proof. If simply by adding an extra 1 to the output whenever we get a machine that we know will halt, we can create a paradoxical machine where we cannot say at all whether the 1 is added or not in its final result, then well, that produces an inherent contradiction that makes the entire existence of our HTM impossible.

[Kythia]

I'm sorry, you have totally lost me here.

I'm anxious not to you know caricature your argument but it seems like you're saying "We can take this thing that works just fine, make it not work by adding an extra one to it and then use that as a proof that it can't possibly work"  I know that's not your point, don't get me wrong, but I honestly don't see where I've misunderstood you.

It seems it doesn't make the HTM qua HTM impossible, it only makes our faulty HTM that adds a one to the end impossible.  Sure we can create a paradoxical machine but that's like me taking a horse and adding scales, cold blood and egg laying to it and then saying "look, a horse can't possibly be a real mammal because it has all of these reptilian features" (Im not a biologist - if that example doesn't work then I hope you can see it as a flaw in the example rather than otherwise)

I'm sorry, I'm really not trying to be dense here.  Feel free to ignore me and I do genuinely appreciate all the help you've given so far.

[Oniya]

This may seem like a tangent, but it relates to the style of argument Stormwyrm is using.

There's a proof out there that proves that the number of decimal numbers (R) is a 'bigger infinite' than the number of natural numbers (N).  The way it works is as follows:

Assume that you can pair up each decimal number between 0 and 1 with a counting number (1,2,3,...)
Imagine a list of these numbers.
Now, create a new decimal number (D) by taking the first digit after the decimal point of the first line and adding one, then the second digit after the decimal point of the second line and adding one, then the third digit after the decimal point of the third line and adding one until you reach the end - taking the Nth digit after the decimal point of the Nth line and adding one.

The new number, D, will be different from every single number already on the list, and even if you tack it onto the very end of the list (making it N+1), you can make a new D by doing the same process.  This means that R is bigger than N, even though both are infinite.

[Kythia]

Yeah I see that - someone (you?) mentioned Cantors diagonal proof and I looked that up.  I don't see how this is a you know subset of that though.

But clearly I need to go away and read theat Goedel Escher Bach book you recommended and spend some time rather than hassling all you lovely people.

[Oniya]

By making the DTM add a 'one' to its output, it makes it a 'new thing' - like the cobbled-together number from Cantor's proof.  The HTM determines if the output will stop.  The UTM is supposed to simulate any Turing machine.  The DTM - like the cobbled-together number - uses the UTM to make a simulation of any Turing machine that halts, only with an added 1.  Therefore, the UTM (which is supposed to simulate any Turing machine) can't simulate the DTM.

[Kythia]

Does that not mean the UTM is impossible though (because I can hypothesise a TM it can't simulate), rather than the DTM? 

Or is that largely a matter of semantics, as it now occurs to me it may be.  A matter of whether we define the UTM as being able to simulate any hypothetical TM - and thus impossible - or as the UTM as being able to simulate any possible TM and thus the modified DTM impossible.

Yeah, that seems like a definitional point.

Awesome.  Thanks

[Vekseid]

Your own computer is a UTM given sufficient storage. Certainly, your own computer has enough space and processing power to simulate itself, and nearly any other machine, even one released say, ten years from now. It will do a horrible job, time-wise, yes. But there's no operation the Wondertron (tm) Ten Trillion can do that your machine, given sufficient storage, cannot. Your grandchildren might die of old age before it completes one second of the Wondertron's output, but they are still translatable.

stormwyrm proposes the HTM. This is a device we call an oracle in computer science terms - it's something we can't build, but we can still work out problems pretending it can exist.

The thing is I'm not sure where storm's argument is rigorous. We can just as well propose an Add-one Turing Machine. The ATM is a UTM that for no particular reason adds 1 to any halted output. So I'm not sure what the problem is with the hypothesized DTM is myself.

[Kythia]

My understanding of stormwyrm's argument - and I stress that the point of this post is to attempt to clea rup my own understanding through explaining it to another rather than an attempt to directly inform you, I find it a useful tool in trying to understand something to attempt to explain it and comp sci aside the one thing I think this discussion has shown is that I don't really know what I'm talking about - is as follows.  However, I did find the proof very confusing so I could well be wrong.

We can imagine a TM that will tell if a given instruction set can be followed to completion or not.  Lets use your terminology and call it an oracle.  Fine and dandy.  This oracle will take one action if the instructions will halt, another if not.

We can then imagine another TM that incorporates the Oracle (I find it easier to think of two machines here than three, but I think the equivalence holds).  This TM accepts a string of instructions.  It first passes them to the Oracle and reads the output from that - if the output shows the problem will never halt it outputs something unimportant.  If the oracle says it won't though, then it processes as normal - the oracle is essentially a pre-checker to prevent the TM halting.

Now, this TM can itself be represented as a series of instructions which can obviously be fed into itself.

What  we can say though is that the oracle is one of a class of machines.  I've glossed over above what input it gives because the general class is that it just outputs something.  One of those potential outputs is the original input with a one appended to the end (or two ones, or 00101000111111010, or whatever).

Feeding a description of our TM (incorporating the oracle) to a UTM fails if we use a type of oracle that returns anything other than the original input.

So far so groovy, although yeah its far from rigorous.  Trivially true, if anything.

What - and here is the point that confused me immensely and that I think (thanks Oniya) I've got my head round - I think stormwyrm's point was that because this second type of the oracle fails it can't be simulated by a UTM.  And because a UTM can simulate any TM, it can't be a real TM.  And because there is no difference in the abstract between an oracle that activates the instructions and one that activates the instructions and appends there is no reason that a UTM would be able to model one member of a general class and not all, therefore the general class is impossible.

That sounds tenuous now I've written it out.  As you say, thats not relevant to the halting problem.  Hmmmm

As I say, I find it useful to attempt to explain as a check I understood and, in this case, apparently I didn't.

[Vekseid]

That's what I was trying to get out of it, but I can't find fault with your original intuition of "Why is it adding a 1 at all?" I cannot see how stormwyrm's proof is rigorous.

Because it's absurd to say that we can't make a machine add a 1 after every halt. Feed the ATM's description into the UTM, and the same 'problem' occurs, but there's no such problem because the UTM's lack of the extra 1 is simply a reflection that the extra 1 is an artifact.


The general proof behind the halting problem is, assume we have a function:
halt(x, y)
Where x is a program and y is its input, in the form of strings (you can pass actual function declarations in many programming languages, but that's not quite what we want to do here).

It returns true if x halts for y, and false if it does not.

So let's create a function, call it
paradox(x) {
  if halt(x, x) { loop forever; }
  else return;
}

So if we call
paradox("paradox(x) {
  if halt(x, x) { loop forever; }
  else return;
}");

If it halts, that means halt(x,x) returns true, in which case it would loop forever, meaning that it wouldn't halt, meaning that it would just exit, meaning that it would halt...

[Kythia]

Bah.  I get your proof, Vekseid:

"Spoilered for presumed lack of anyone caring.

Putting your programs into Turing Machine terms then... let's see.

First we have an unnamed Turing Machine which I'll call 'Kythia'  It take a string of input, y.

We then have a 'halt' turing machine.  It takes as its input a TM and it's input.  It returns true if the TM would halt. 

In your terms, halt(kythia, y).  In mine, feed the results of running y through kythia into halt.

Now lets have a third.  'paradox'  It takes a TM into it, loops forever if that program halts, returns true if it doesn't.

so paradox(halt(kythia,y)) would run forever if kythia,y would halt and would halt if kythia, y would run forever.  Perhaps not useful, but sure, I can rock that.

So feeding that TM, 'paradox', back into itself gives the result you say.  It'll halt if it runs forever and if it runs forever it'll halt, which is impossible.

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.

When Goedel Escher Bach hits the top of the list I'll take another look at this but I suspect its gonna still elude me.  Thank you for your time everyone.  I realise getting an idea into my blonde head - from a bottle but nevertheless - was a huge effort for you but if its worth anything I enjoyed myself.

[Oniya]

Thank you for your time everyone.  I realise getting an idea into my blonde head - from a bottle but nevertheless - was a huge effort for you but if its worth anything I enjoyed myself.

I always enjoy talking math - so it was mutually enjoyable