# What is an algorithm (in programming terms)?

• (2 Pages)
• 1
• 2

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

### #1 CheckersW

Reputation: 12
• 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

• Games, Graphs, and Auctions

Reputation: 12243
• Posts: 45,332
• 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.

### #3 spiderninja

Reputation: 2
• 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.

### #4 mostyfriedman

• The Algorithmi

Reputation: 729
• 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

### #5 Nikitin

• D.I.C Regular

Reputation: 56
• 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.

### #6 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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

### #7 Nikitin

• D.I.C Regular

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

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

Posted 09 March 2011 - 10:15 AM

lordofduct, 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.

### #8 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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?

### #9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12243
• Posts: 45,332
• Joined: 27-December 08

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

Posted 09 March 2011 - 10:35 AM

Obviously recursion came first.

### #10 Nikitin

• D.I.C Regular

Reputation: 56
• 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.

### #11 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

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

Posted 09 March 2011 - 11:29 AM

Nikitin, 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.

### #12 Nikitin

• D.I.C Regular

Reputation: 56
• 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

### #13 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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

### #14 Nikitin

• D.I.C Regular

Reputation: 56
• 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.

### #15 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• 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'.