[Nikitin]

lordofduct, on 09 March 2011 - 03:40 PM, said:

Well I shutter to ever go to the school you went to if your professors use a line of logic deriving that 'all algorithms are Turing machines' from 'Turing machines define algorithms'.

You wouldn't get in. It's a top ranked CS department in the world.

Sorry, couldn't resist.

This post has been edited by Nikitin: 09 March 2011 - 02:44 PM

[lordofduct]

oh my, I wouldn't make it into your unknown school... boo hoo.

What school is it, top ranked per whom? What Carnegie Mellon, Berkley, MIT, who? You might be surprised to find out where I could be accepted.

You know what, nevermind, I don't need to know. Because i don't attempt to lower to such perceived low blows. Enjoy your shiny piece of paper, a piece of paper I still would shutter to gain if it was from professors like yours. But I have a feeling they don't actually agree with your statement that all algorithms are Turing machines. I bet they agree with the other part, the part I agree with as well, and that's a Turing machine defines a computer algorithm.

This certainly means a Turing machine exists for the algorithm. But to say that this means the algorithm is a Turing machine is a brash over simplification. And the existence of this statement in computer science is meant to be an over simplification. The statement is to mean that the some Turing machine can be described to process this algorithm. But I mean come on, to what effect is toting that as some definition for algorithm... what use is that!?

This post has been edited by lordofduct: 09 March 2011 - 03:17 PM

[hookiethe1]

In my mind, an algorithm is just like a mathematical formula, but it uses logic.

And for the sake of the debate, a couple of quotes from Sipser's "Introduction to the theory of Computation."

"Informally speaking, an algorithm is a collection of simple instructions for carrying out some task."

"...the Turing machine merely serves as a precise model for the definition of an algorithm."

Helpful?

[lordofduct]

Quote

"...the Turing machine merely serves as a precise model for the definition of an algorithm."

I couldn't say it any better!

[hookiethe1]

It's a good book, wish I understood everything in it!
I'm hoping when I get to my master's I get a chance to revisit computation theory, there's lots of interesting shit going on there.

[Nikitin]

Ok, so you agree that every single algorithm has an equivalent TM that does exactly what the actual algorithm does.

I'm sure you can also agree that a TM, unlike the conceptual notion of algorithm, has a very formal definition that can rigorously studied with all power of math.

However, it looks like what you don't agree with, is using algorithm and its equivalent TM interchangeably. Well, that's what people do in academia. Sipser, whose quote (which is of course true, I studied from that book, every single page) you like so much, also said in that same chapter that Church-Turing thesis gave us the definition of algorithm that wasn't there before.

Then you asked this question...

Quote

The statement is to mean that the some Turing machine can be described to process this algorithm. But I mean come on, to what effect is toting that as some definition for algorithm... what use is that!?

Get Sipser's book, and study it (do the exercises!). Then you'll understand how silly that question is and you'll understand what I was talking about all along. Reading Wikipedia for an hour, and trying to give your loose English interpretations to what you see is not a substitute.


Peace.

This post has been edited by Nikitin: 09 March 2011 - 04:49 PM

[lordofduct]

What I don't agree with is equating algorithm to TM. I don't care if people use it interchangeably in academia, but when you dig down it's understood that they aren't exactly the same thing and just because one uses the two words interchangeably doesn't mean they are equal.

For an analogy lets take a much more simple mathematical principle. Tangents and derivatives. A derivate defines the tangent of a curve, and the words tangent and derivative are used interchangeably, but that doesn't make a tangent a derivative. (in this analogy think of derivative as TM, and tangent as algorithm).

And most importantly to just come out and say:

"tangent is a derivative"

is useless, you've done nothing to explain what a tangent really is unless you know what a derivative is, and if you know what a derivative is, you probably know what a tangent is.

This same thing goes for algorithm. Saying:

nikitin said:

Since this topic is in Computer Science section, the first thing that should have been said is:

Algorithm is a Turing machine.

does nothing to explain what an algorithm is for the reader unless they know what a Turing machine is, and if they know what a Turing machine is, then they already know what an algorithm is!



[appended]
I would like to reverse for a second for the sake of anyone else reading this debate/discussion. This goes back to your speculation that I'd be unable to enter your school.

I would hope any high ranking school wouldn't bar a student for 1) questioning what the professor says, nevermind question what a student/alumni says, or 2) being wrong. Usually someone applying to a school doesn't have all the knowledge that the school is going to teach them, if they did, they wouldn't need the school.

This post has been edited by lordofduct: 09 March 2011 - 06:07 PM

[ccubed]

Nikitin, on 09 March 2011 - 01:17 PM, said:

Wait, you want to start arguing that algorithms did have a formal definition because Kleene came up with one... several years before Church? I'm not into such things.

As far as I know, the whole period of 1930 - 1940 was just a bunch of scientists working together on the same issue, some coming up with their own versions which in the end became either debunked or equivalent. The biggest thing that all of us got out it was Church-Turing thesis.

Whether or not it was a formalized period of research into computer science and its equivalent methods doesn't matter. It was still research pertaining and that makes it as valid as any other modern day CS research. Science evolves itself.

Nikitin, on 09 March 2011 - 01:17 PM, said:

lordofduct said:

A computer algorithm, formally, must be able to be simulated by a Turing complete machine. This does not mean all algorithms have an unique and exclusive TM associated with it, only that a Turing complete machine can simulate it. A Turing complete machine is capable of operating all sorts of algorithms, not just one. So this statement of yours would be like saying that because the word 'the' is associated with
the English language, then the word 'the' is an English language.

You're mistaking the set of all TM with a set of equivalent TMs. Here would be a good time to learn the definition of TM, by the way.

For each algorithm there is class of equivalent Turing machines that simulate that algorithm only. Just that algorithm and nothing else. For any input, both produce the same exact outputs. Define algorithm to be that class of Turing machines.

This shows a misunderstanding of the terms.

An algorithm is a series of defined steps to accomplish a goal.

A Turing machine is something that can simulate an algorithm and its results for any input.

How often do you refer to the Bubble Sort Algorithm by its equivalent Turing Machine? Probably never. Reason being, the algorithm defines the steps to perform a bubble sort, the Turing machine simply simulates the output of that algorithm given a certain input.

Nikitin, on 09 March 2011 - 01:17 PM, said:

lordofduct said:

Sorry, it is circular reasoning. I did insinuate it is that, because that's what it is.

Algorithms are Turing machines, that's how Turing machines define algorithms, which are Turing machines, which define algorithms, which are Turing machines, that define algorithms, which are Turing machines... ad nauseum.

A = Algorithms are Turing machines
B = Turing machines define algorithms

A -> B

Algorithms are TM. From that it follows that Turing machines define algorithms.

How hard can it be?

No, algorithms are not Turing Machines.

Just because the test for an algorithm is that it must be capable of being simulated by a turing machine does NOT mean that algorithms are Turing Machines.

Following your logic, it would be the same thing as saying 'Because my Monitor must connect to my computer to be useful, it must be a computer.' And we all know how that statement is wrong.

[Nikitin]

The formal definition of algorithm is that it is a computable function, which Church-Turing Thesis has shown is equivalent to a Turing Machine. This is the mathematical definition, which gives us insights into what algorithms actually are, and what allows us to use mathematics to study them. Note that Turing Machines themselves are not defined in terms of algorithms (which would make sense, since Turing came up with them to describe what algorithms are in the first place!).

Quote

The notion of algorithm itself was not defined precisely until the 20th century...

Alonzo Church and Alan Turing in 1936 came with formal definitions for the concept of algorithm. Church used a notational system called lambda-calculus to define algorithms. Turing used his "Turing Machines" to define algorithms. These two definitions were shown to be equivalent.

Other formal definitions of algorithms have been provided... Essentially all these concepts of algorithm are equivalent among them, and are equivalent with Turing Machines.

---- SUNY SB, lecture

One might (though I can't see anyone bothering to argue about this) say that algorithm is a function but a Turing Machine is a tuple, but for the most part:

Quote

Sometimes algorithms are simply equated with Turing Machines...

Mathematicians and computer scientists sometimes sharply restrict the definition of "algorithm". They take the definition of "algorithm" given here, and use it to define the notion of an effective procedure. Then they define an algorithm as an effective procedure that always halts or terminates.

--The MIT encyclopedia of the cognitive sciences.

The last sentence means that the definition of algorithm sometimes is restricted to be a Turing Machine that always halts (a decider).

You can look in chapter 3 of Sipser's textbook for a further clarification if you want.

Now, don't take offense, but, if you think that

ccubed, on 19 May 2011 - 01:27 PM, said:

A Turing machine is something that can simulate an algorithm and its results for any input.

Is a formal definition of a Turing Machine. And if you think that

ccubed, on 19 May 2011 - 01:27 PM, said:

An algorithm is a series of defined steps to accomplish a goal.

Is a formal definition of... anything, then you should learn the basics of Theory of Computation, before trying to argue about Theory of Computation. I mean, it's like me and you are arguing about integrals in Calculus, and you not knowing what an integral actually is. It just doesn't make sense.

To answer your last question - no, I don't define Bubble Sort in terms of its Turing Machine. It's impractical. In virtually all practical situations we can get by with an informal definition of an algorithm - finite number of steps. Practice and theory are often like that.

[lordofduct]

I'd just like to point out this line you quoted from the MIT encyclopedia...

Quote

Sometimes algorithms are simply equated with Turing Machines...

And equate it back to my previous post. (And yes, I believe all the text you cut with that ellipsis lends in as well... for others you can get the breadth of what he is quoting here: Page 11 of MIT Encyclopedia of the cognitive sciences)

This post has been edited by lordofduct: 14 June 2011 - 08:26 AM

[stackoverflow]

I can sum this up.

An algorithm is a set of clearly defined steps to arrive at a solution or a non-solution (sometimes). Not all algorithms have solutions. Some algorithms find a solution some of the times. Some algorithms will never find a solution. Some algorithms are deterministic. Some are non-deterministic.

A harder question is, "What's the difference between an algorithm and a heuristic?"

The answer isn't too hard to grasp. An algorithm is clearly defined-- specific steps. A heuristic is like an algorithm but the steps are not clearly specified.