News:

Main Menu

Turing Complete - huh?

Started by Kythia, November 04, 2012, 07:22:07 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Kythia

So.  I've run up on the phrase "Turing Complete" as it applies to programming languages a couple of times in the last week.  I've read the wikipedia article but I can't make head nor tail of it.  Is anyone capable of explaining it in words of not more than one syllable?
242037

Moraline

#1
I'm just guessing here on my answer. My area of expertise is in systems management and not programming. (Maybe someone else with programming experience can weigh in on the topic as they were taught it.)

I think the issue you might be having is that the phrase has several meanings within the context of computer programming.

The simplest explanation would be that "Turing Complete" means that a program is able to duplicate the function of another program.

Simple Example:

I create a program "A", and it is able to act like a calculator.

Or more complex:

Program "A" is able to replicate human speech (like a reading program.)

Multi-Complex:

Program "A" is able to act like a calculator and replicate human speech as it reads you back the equation and answer.

According to the Wiki article a Turing Machine is a device that is capable of infinite amount of data storage and retrieval. Which makes it possible for the program itself to replicate any mathematical function to the point that it is capable of replicating the actions of any other possible computer program.


*Edit: I should note that Turing completeness is less of a programming issue and more of a mathematical concept and as such is far more complex. It explores the concept of infinite calculations.

Moraline

#2
Quote~ http://en.wikipedia.org/wiki/Turing_completeness
Turing completeness is an abstract statement of ability, rather than a prescription of specific language features used to implement that ability. The features used to achieve Turing completeness can be quite different; Fortran systems would use loop constructs or possibly even goto statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use recursion.

Now with this I'm questioning my previous answer.

Does this mean that Turing Complete refers to the programming language itself only? Not the program created.

Which would mean that Turing Complete would simply mean that a user can create an infinite loop with the program itself?

Example

<If input equals "0" go to "1">
<If answer returns "1," then input equals "0">

.... looping madness ensues.... and computer program usually crashes.

Kythia

Yeah, thi is how I tied myself up in knots as well.  I'm far from being a programmer but surely being able to create an infinite loop isn't that, you know, great or desirable a feature?  Like, sure it might be an indicator of another thingie but in and of itself?
242037

Moraline

#4
I'm not 100% certain on this but a loop allows the program to be able to come up with "best possible answers."

It's a sort of reasoning function. You can't always have a perfect answer so sometimes it needs to give you an answer that is the best fit or something.

Ex:

Search in Google for "George Bush."   There are millions of results. With most popular and best fit answers at the top.

For the program to give you those answers it needs to loop through itself repeatedly and pull out everything that remotely fits the inquiry.

It sounds like the program could just search for every occurrence of "George Bush" in it's data base but that would not give it the best or more likely answers.

So, instead the program runs through every answer that matches then because the loop is still open and running another routine (sub routine) will be triggered by the loop and start adding programming statements.

Computer program does this:

Search "George Bush"

<loops>
<finds all answers... continues to run>
<automatically adds, sort by functions (date, most viewed, etc...)>


((Then it looks for additional statements on the search))

<Was there a "," or a "?" or a ":">

So as the program loops through and keeps searching it uses all of these functions and possible functions to build a database of answers for the inquiry.

In a search engine that gives you a list of results but in other computer programs it will act as a sort of artificial intelligence (AI) and return a single most likely result.

(( Again these are just my thoughts on the subject. It's been years since I've done any sort of programming other then a little web dev stuff.))

*Edit* To add to that. A Turning Complete program would allow these statements and a Non-Turning Complete program would be incapable of making any calculation that wasn't either a 100% yes or no. Those types of programs would simply fail when asked any question that wasn't directly in it's programming already. It would have no ability to integrate with other systems unless it was completely rewritten. It would have no ability to make a decision(formulate answers) based on any sort of abstract information.

Oniya

Quote from: Kythia on November 04, 2012, 08:13:56 AM
Yeah, thi is how I tied myself up in knots as well.  I'm far from being a programmer but surely being able to create an infinite loop isn't that, you know, great or desirable a feature?  Like, sure it might be an indicator of another thingie but in and of itself?

I don't think it has to do with creating infinite loops, but the ability to reduce problems to smaller functions.  For example, if I know the subroutine of 'Raise to a Power', then I can use it to solve the problem 'Find volume of Sphere'.  This article goes into the deeper math of it.  (Turing completeness is a special case of Turing reducibility.)
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

stormwyrm

#6
Turing-complete as an adjective when describing programming languages simply means that it is capable of computing any function that can be computed using a Turing machine (recursively enumerable function). Equivalently, we could also say that the programming language or system is capable of simulating or being simulated by a Turing machine. Then, the question becomes what a Turing machine actually is. It's essentially the simplest model of a general-purpose computer possible, devised by Alan Turing so as to make it possible to reason about the process of computation itself without getting bogged down in the practical details of physical computers. A simple description of a Turing machine is a tape, with an unlimited number of spaces on which symbols can be written or overwritten, a tape head that marks the current position of the machine, and a set of states where the machine may be in. At any given time, the machine is in one of its possible states, and it can do any or all of the following things:

  • Stop processing
  • Overwrite the symbol on the tape head with a new symbol
  • Move the tape head to the left or to the right
  • Go to a different state
This is the simplest possible model of fully general-purpose computation that has been devised. It has been proved that these simple things suffice to simulate every possible model of computation out there. It is enough to compute everything every computer everywhere in the world that has ever been built can compute (the question of whether it can do so efficiently is another matter of course, and that gets into details we don't consider here).

It becomes possible to prove certain interesting things about what functions can be computed by a Turing machine, in fact, it can be shown that certain functions cannot be so computed, i.e., a Turing machine trying to compute them might never stop, and there'd be know way of knowing whether it ever would, but that's another story.

Well, I took a graduate-level course in the Theory of Computation a few years back, so I think I'd know about these things. XD
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Kythia

Right, I think I get that.

So in essence a Turing Complete language is one that can do anything a computer language can do.  I read about the halting problem and I get that so lets pretend thats the only thing a Turing machine can't do (I realise thats likely a simplification but bear with me).

What you're in essence saying is that a Turing Machine can do anything except work out whether a loop would be inifinite and any language that is Turing Complete is capable of doing the same?
242037

stormwyrm

Quote from: Kythia on November 04, 2012, 11:11:46 AM
Right, I think I get that.

So in essence a Turing Complete language is one that can do anything a computer language can do.  I read about the halting problem and I get that so lets pretend thats the only thing a Turing machine can't do (I realise thats likely a simplification but bear with me).

What you're in essence saying is that a Turing Machine can do anything except work out whether a loop would be inifinite and any language that is Turing Complete is capable of doing the same?

Precisely. Note that there are also computational systems that have less power (i.e. they are less general) than the Turing machine, e.g. finite automata, which are just a bunch of states that have no ability to change the symbols on their input, push-down automata (which have an unlimited scratch area where they can write temporary results but no ability to change the symbols on their input either), and linear bounded automata (almost like Turing machines except that the number of tape slots available to them is limited). A Turing machine is capable of simulating them all, and at the same time, it is possible to also construct a Turing machine capable of simulating any other Turing machine (the so-called universal Turing machine). No one has yet come up with a computational system capable of computing something that a Turing machine cannot.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Oniya

Quote from: stormwyrm on November 04, 2012, 11:21:44 AM
No one has yet come up with a computational system capable of computing something that a Turing machine cannot.

That would probably set Goedel spinning in his grave, if they did.  ;)
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Kythia

Awesome.  Thanks a lot all.

*Kythia crosses "Turing Complete" off the list of things she doesn't understand and cermoniously writes it onto the list of things she does.  THen googles Goedel*
242037

Oniya

If you find this sort of thing interesting, and have a local library that carries it, I'd recommend 'Goedel, Escher, Bach - The Eternal Golden Braid'.  Also, anything by Rudy Rucker.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Kythia

I like to think I find most things interesting.  I have a list of books I need to read so I'll stick that on the list. 
242037

stormwyrm

If you want a fictional story that deals with this in a way, you may also like to check out Neal Stephenson's Cryptonomicon. Stephenson goes into rather extensive detail about Turing machines (Alan Turing himself appears as a minor character).
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Kythia

Funnily enough that's already working its way up my list of books.  Don't recall who recommended it, but its on there.  Between Stalingrad and City of God, if you care.
242037

Vekseid

Quote from: Kythia on November 04, 2012, 11:11:46 AM
Right, I think I get that.

So in essence a Turing Complete language is one that can do anything a computer language can do.  I read about the halting problem and I get that so lets pretend thats the only thing a Turing machine can't do (I realise thats likely a simplification but bear with me).

What you're in essence saying is that a Turing Machine can do anything except work out whether a loop would be inifinite and any language that is Turing Complete is capable of doing the same?

I think this is more simplification than is good. A Turing machine is capable of evaluating some infinite loops:

while (1) { continue; }

Is an obvious example. The halting problem refers to the general case, and it is possible to create programs which are not subject to such because they never execute instructions that permit the full general case to go on unattended. Our own brains suffice as an example - we can choose to give up on trying to solve a problem.

Generally, if some computational model is considered not Turing complete (outside of the bounds of finite storage), this is considered to be a flaw.

An example was early understanding of neural networks. A single-layer of perceptrons (rod and cone cells in your eye would be an example of such a single layer) is not capable of computing a XOR (exclusive or) operation.

So a single-layer neural network is not Turing Complete.

Obviously, humans can perform the XOR operation. Of course, obviously, human thought processes involve dozens to hundreds of layers of neural networks, so the jury was 'out' until someone proved that yes, a multi-layer neural network was Turing Complete.


Kythia

Riiiiiight.

I'm gonna take a wild stab and say "Thank you" but honestly Vekseid (Hi, by the way) its gonna take me a bit of reading to do more than smile and nod vaguely at that.  While it may be an obvious example to you, you know....

Thank you though, it'll guide tonight's shameless autodidacticism
242037

Vekseid

You can always ask more questions. : )

A XOR operation is simply one that takes two inputs, which can be true or false, and returns true if and only if exactly one of the inputs is true, and false otherwise.


Oniya

The best descriptive example of an XOR that I've found is a light that is controlled independently by a switch upstairs and a switch downstairs.  That is, someone on either floor can control the light regardless of the position of the other switch.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Vekseid

And 'doh, forgot about the loop.


while (1) { continue; }


This is simply the tightest infinite loop you can make (possibly excepting the continue, but some compilers may spot it otherwise and go 'wtf you doing!?'). It has no input whatsoever, meaning the block can be evaluated once, independently, and if it does not break out of the loop somehow, that means that it will not halt. If it does break out of the loop, that means it will halt.

Since the block inside the loop is just a continuation, there's no way to break out. So we can know that it is an infinite loop trivially without running it.

Similarly, we can expand this to include functions with limited bounded inputs. Basic addition is one example, etc. The process of evaluating functions for such fitness is referred to as formal proving.

You cannot prove every program simply because not every mathematical statement is provable (per Goedel described above). But you are not required to attempt such mathematical wizardry to program. Often you just want something that will do basic math really fast and really cheaply.

Kythia

Quote from: Vekseid on November 04, 2012, 04:56:31 PM
You can always ask more questions. : )

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.

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

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?

Sorry if I appear dense.  This is brand new ground for me.

And thank you for your answers.  I promise I won't sulk if you abandon me.
242037

Oniya

Actually, in that case, it's a case of different wiring.  In my example, flipping the switch at the bottom of the stairs when the light is on should turn it off, and vice-versa.  Likewise, flipping the switch at the top of the stairs when the light is on should turn it off, and vice-versa.  (We actually had to construct this circuit in a science lab I was in.)  Both switches up, light is off.  Both switches down, light is off.  Either one up and the other down, light is on. 
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Kythia

Ah right.  I have clearly defined "on" and "off" positions on my lightswitches so I guess they did it like that deliberatly.  So you're saying the light is only on if one switch is up and one down - both up or both down means off.  Sure, I can picture that.
242037

Oniya

That's an XOR situation.  Practically, it means that you can control the light whether you're upstairs or downstairs, no matter what position the other switch is in.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Kythia

Gotcha.  And perceptrons - about half way through the wikipedia article on 'em - can't handle that sort of situation when there's only a single layer of them, therefore a single layer of perceptrons isn't Turing complete, therefore a single layer of perceptrons isn't capable of doing everything a turing machine can?
242037

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.
242037

Oniya

Right.  The XOR has to know that one and only one input is 'on'.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Vekseid

Quote from: Kythia on November 04, 2012, 05:44:49 PM
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.

Quote
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.

Quote
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.

Quote from: Kythia on November 04, 2012, 06:19:10 PM
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.

Quote
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

Quote from: Vekseid on November 04, 2012, 06:53:09 PM
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.

Quote from: VekseidYou'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.

Quote from: VekseidAnd 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.

Quote from: VekseidIt'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.
242037

Vekseid

Quote from: Kythia on November 04, 2012, 07:18:28 PM
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.

Quote
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. : )

Quote
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.

Quote
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

#30
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
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

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.
242037

stormwyrm

Quote from: Kythia on November 05, 2012, 04:07:34 AM
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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Kythia

#33
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.
242037

Moraline

#34
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

#35
Quote from: Moraline on November 05, 2012, 07:00:49 AM
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.

Quote
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.

Quote
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.

Quote
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.

Quote
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.

Quote
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

Quote from: Vekseid on November 05, 2012, 08:22:32 AM
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.) 
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Moraline

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




Vekseid

Quote from: Oniya on November 05, 2012, 08:42:00 AM
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

Quote from: Kythia on November 05, 2012, 06:52:56 AM
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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

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.
242037

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.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

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.
242037

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.
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

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
242037

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.
242037

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.
242037

Oniya

Quote from: Kythia on November 06, 2012, 05:50:19 PM
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 :-)
"Language was invented for one reason, boys - to woo women.~*~*~Don't think it's all been done before
And in that endeavor, laziness will not do." ~*~*~*~*~*~*~*~*~*~*~Don't think we're never gonna win this war
Robin Williams-Dead Poets Society ~*~*~*~*~*~*~*~*~*~*~*~*~*~Don't think your world's gonna fall apart
I do have a cause, though.  It's obscenity.  I'm for it.  - Tom Lehrer~*~All you need is your beautiful heart
O/O's Updated 5/11/21 - A/A's - Current Status! - Writing a novel - all draws for Fool of Fire up!
Requests updated March 17

Vekseid

Quote from: Kythia on November 06, 2012, 05:50:19 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?

Quote from: Oniya on November 06, 2012, 05:59:06 PM
I always enjoy talking math - so it was mutually enjoyable :-)

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



stormwyrm

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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

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.

stormwyrm

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?
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

Quote from: stormwyrm 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)).

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.

stormwyrm

#55
Quote from: Vekseid on November 06, 2012, 11:05:16 PM
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
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

Quote from: stormwyrm on November 07, 2012, 12:24:26 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.

stormwyrm

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?
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

Quote from: stormwyrm on November 07, 2012, 01:26:12 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.

stormwyrm

Quote from: Vekseid on November 07, 2012, 01:32:38 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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

Where are you forcing the cycle to continue? That would be a valid and possibly novel example of the paradox if you forced that.

stormwyrm

#61
Quote from: Vekseid 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.

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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

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.

stormwyrm

Quote from: Vekseid 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.

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!

Quote from: Vekseid on November 07, 2012, 07:01:42 AM
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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

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.


stormwyrm

Quote from: Vekseid 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()

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.

Quote from: Vekseid on November 07, 2012, 07:59:42 AM
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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

Quote from: stormwyrm on November 07, 2012, 08:25:40 AM
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.

stormwyrm

Quote from: Vekseid on November 07, 2012, 10:14:34 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!

Quote from: Vekseid on November 07, 2012, 10:14:34 PM
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.
If there is such a phenomenon as absolute evil, it consists in treating another human being as a thing.
O/OA/A, Requests

Vekseid

I honestly have no idea what you are trying to say, to be perfectly frank.