25 Replies  34355 Views  Last Post: 12 July 2011  12:48 AM
#1
What is an algorithm (in programming terms)?
Posted 20 February 2011  09:16 PM
If not, it'd be awesome if you could give a simple definition (no need for detailed answers; this is just for general learning)
Replies To: What is an algorithm (in programming terms)?
#2
Re: What is an algorithm (in programming terms)?
Posted 20 February 2011  09:19 PM
#3
Re: What is an algorithm (in programming terms)?
Posted 21 February 2011  12:00 PM
#4
Re: What is an algorithm (in programming terms)?
Posted 21 February 2011  12:18 PM
Algorithms + data structures = computer programs
#5
Re: What is an algorithm (in programming terms)?
Posted 08 March 2011  09:22 PM
Algorithm is a Turing machine.
#6
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  08:25 AM
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  10:15 AM
lordofduct, on 09 March 2011  09:25 AM, said:
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  10:31 AM
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
so Turing machines defined algorithms... but algorithms are Turing machines? Which came first, the chicken or the egg?
#9
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  10:35 AM
#10
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  11:01 AM
Quote
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
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  11:29 AM
Nikitin, on 09 March 2011  11:01 AM, said:
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:
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
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
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  12:17 PM
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 ChurchTuring thesis.
Quote
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
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  12:27 PM
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
defined by does not make it one, it makes it defined by
Quote
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  02:15 PM
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
Re: What is an algorithm (in programming terms)?
Posted 09 March 2011  02:40 PM
