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