What is an algorithm (in programming terms)?

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 30536 Views - Last Post: 12 July 2011 - 12:48 AM

#1 CheckersW  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 198
  • Joined: 04-April 09

What is an algorithm (in programming terms)?

Posted 20 February 2011 - 09:16 PM

I've never really understood what an algorithm is in relation to programming. Would it be fair to say that a function (for example, one which determines if the user's Date of Birth is valid to let them view a video) is an example of an algorithm?

If not, it'd be awesome if you could give a simple definition (no need for detailed answers; this is just for general learning)
Is This A Good Question/Topic? 0
  • +

Replies To: What is an algorithm (in programming terms)?

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,256
  • Joined: 27-December 08

Re: What is an algorithm (in programming terms)?

Posted 20 February 2011 - 09:19 PM

The best definition of an algorithm I've heard is that it is a finite sequence of steps that solves a specific problem. :)
Was This Post Helpful? 4
  • +
  • -

#3 spiderninja  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 10
  • Joined: 03-December 10

Re: What is an algorithm (in programming terms)?

Posted 21 February 2011 - 12:00 PM

That is a good question. When I think of an algorithm, I always think of data structures. Eg, sorting algorithms but I know there are other types. I'd love to hear of an example which did not refer to a data structure.
Was This Post Helpful? 0
  • +
  • -

#4 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: What is an algorithm (in programming terms)?

Posted 21 February 2011 - 12:18 PM

Data structures are merely a way to represent data for efficient retrieval, insertion, and deletion. An Algorithm on the other hand is just a recipe for solving a problem. In general

Algorithms + data structures = computer programs
Was This Post Helpful? 1
  • +
  • -

#5 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: What is an algorithm (in programming terms)?

Posted 08 March 2011 - 09:22 PM

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

Algorithm is a Turing machine.
Was This Post Helpful? 0
  • +
  • -

#6 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2538
  • View blog
  • Posts: 4,641
  • Joined: 24-September 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 08:25 AM

wouldn't that actually be the other way around...

A Turing machine can represent any computer algorithm.

... it's actually kind of the definition of a Turing machine.

This post has been edited by lordofduct: 09 March 2011 - 08:25 AM

Was This Post Helpful? 0
  • +
  • -

#7 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 10:15 AM

View Postlordofduct, on 09 March 2011 - 09:25 AM, said:

wouldn't that actually be the other way around...

A Turing machine can represent any computer algorithm.

... it's actually kind of the definition of a Turing machine.


No that's not a definition of a Turing machine. It's something that had to be proved. The whole point for Turing machines is that they finally provided us with a formal definition of algorithms. Before that, algorithms didn't have it.
Was This Post Helpful? 0
  • +
  • -

#8 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2538
  • View blog
  • Posts: 4,641
  • Joined: 24-September 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 10:31 AM

algorithms had a formal definition before 1937.

The id of a Turing machine described a "Turing computable algorithm"... and computer algorithms are considered valid if they are "Turing computable". So a Turing machine should be able to describe any computer algorithm.

This does not mean algorithms (not even computer algorithms) are Turing machines.

Quote

The whole point for Turing machines is that they finally provided us with a formal definition of algorithms. Before that, algorithms didn't have it.


so Turing machines defined algorithms... but algorithms are Turing machines? Which came first, the chicken or the egg?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,256
  • Joined: 27-December 08

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 10:35 AM

Obviously recursion came first. ;)
Was This Post Helpful? 2
  • +
  • -

#10 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 11:01 AM

What was the formal definition of an algorithm before Turing and Church came up with theirs?

Quote

So a Turing machine should be able to describe any computer algorithm.

This does not mean algorithms (not even computer algorithms) are Turing machines.

I think it does. Every algorithm has an associated TM. Any algorithm, therefore, can be simply defined as such TM (or class of equivalent TMs if you will).

Quote

so Turing machines defined algorithms... but algorithms are Turing machines? Which came first, the chicken or the egg?

What? This is not circular reasoning if that's what you're getting at. Yes, algorithms are Turing machines. That's how TMs define algorithms.
Was This Post Helpful? 0
  • +
  • -

#11 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2538
  • View blog
  • Posts: 4,641
  • Joined: 24-September 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 11:29 AM

View PostNikitin, on 09 March 2011 - 11:01 AM, said:

What was the formal definition of an algorithm before Turing and Church came up with theirs?


First you need to slim that down a bit... algorithm is a word that has been around for just about as long as recorded history. Ancient Greece, early Middle East, India, all had some version of the word and a formal definition used with the word for the purposes of mathematics. It's not called Euclid's Algorithm for shits and giggles.

Are you speaking specifically of 'computer algorithms'? The definition of computer algorithms was formed more recently because computers are a more recent technology. The formal definition of which started forming in the early 20th century before Turing's ideas were devised. The modern definition was influenced by many inputs, including the Turing machine, but not exclusive to the Turing machine.

Just for the sake of debate I pulled up a quick source, and if you have information debunking it, please edit the wikipedia article.

wikipedia said:

A partial formalization of the concept began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability"[8] or "effective method";[9] those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939.


yes I know the broad opinions of Wikipedia, but it's just a quick source, and as I said... if you know better, then do edit it please!






Quote

Quote

So a Turing machine should be able to describe any computer algorithm.

This does not mean algorithms (not even computer algorithms) are Turing machines.

I think it does. Every algorithm has an associated TM. Any algorithm, therefore, can be simply defined as such TM (or class of equivalent TMs if you will).


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.


Quote

Quote

so Turing machines defined algorithms... but algorithms are Turing machines? Which came first, the chicken or the egg?

What? This is not circular reasoning if that's what you're getting at. Yes, algorithms are Turing machines. That's how TMs define algorithms.


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.
Was This Post Helpful? 0
  • +
  • -

#12 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 12:17 PM

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.

Quote

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.


Quote

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?

This post has been edited by Nikitin: 09 March 2011 - 12:19 PM

Was This Post Helpful? 0
  • +
  • -

#13 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2538
  • View blog
  • Posts: 4,641
  • Joined: 24-September 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 12:27 PM

for the sake of discussion, from here on out when I say 'algorithm' I mean 'computer algorithm', and I assume that's what you've meant all along.



I accept your claim that Turing machines define algorithms. It is part of the definition of algorithms... that they can be simulated by a Turing complete machine.

I forfeit your claim that algorithms are Turing machines as false. And that your claim because Turing machines define algorithms then algorithms as Turing machines to not be logically sound with out more data. The idea that an algorithm can be a TM, does not mean all algorithms are TMs. And it certainly doesn't mean that the definition of algorithm is that they are TMs.

algorithm: a computer algorithm must be able to be simulated by a Turing complete machine


quoting wikipedia again, which quotes more modern doctors... which actually say one half of what you say... the very half I agree with. This also is a more modern thesis though.

Quote

Gurevich: "...Turing's informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine ... according to Savage [1987], an algorithm is a computational process defined by a Turing machine"


defined by does not make it one, it makes it defined by


Quote

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

A -> B

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


Turing machiens define algorithms, that's the thesis. And A does not prove B, A is an independent thesis, which has yet to have any proof from you. A doesn't need to prove B, B already has supported statements unrelated to A, hence why it's independent.

Nevermind that A does not imply B.

Algorithms are Turing machines, so thusly Turing machines define algorithms? Huh? What logical method are you using here?

And even if A DID impy B, it doesn't prove A. A is the part that's unfounded... B has already been supported. That's why implication uses the -> symbol, it's unidirectional.

To say if A implies B, then B implies A... that's circular reasoning, by definition.

This post has been edited by lordofduct: 09 March 2011 - 12:43 PM

Was This Post Helpful? 0
  • +
  • -

#14 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 02:15 PM

I honestly don't even know what your point is and what is this "computer algorithms vs algorithms" thing you're on. In academia:

When you hear a person talking about "computer algorithm", he/she is talking about "algorithm".
When a person is talking about an algorithm, he/she is talking about a Turing machine.

There's some cloud of informality around this, and you can interpret it any way you want. I (and every professor I talked to) interpret this as "algorithm is a Turing machine". You can call this relationship whatever you want.
Was This Post Helpful? 0
  • +
  • -

#15 lordofduct  Icon User is offline

  • I'm a cheeseburger
  • member icon


Reputation: 2538
  • View blog
  • Posts: 4,641
  • Joined: 24-September 10

Re: What is an algorithm (in programming terms)?

Posted 09 March 2011 - 02:40 PM

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'.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2