So one can say a language is Turing complete if it meets some criteria and it can do anything another Turing complete language can do.
Does that mean I can theoretically implement Google using Javascript or Brainf_ck?
+1
A:
Yes, anything they can compute, you can do in those languages. But this says nothing about the amount of memory or other storage required, how fast it will run, or the ease of writing or debugging it.
poolie
2010-09-11 01:12:52
We'll get Chuck Norris to write the code, then we can skip the debugger...
Thorbjørn Ravn Andersen
2010-09-27 15:56:09
+1
A:
You can implement Google from a stack machine made of matchboxes and rocks. Yabba-Dabba-Doo?
mhambra
2010-09-11 01:15:12
Sure you can, as long as you have infinite tape and patience.
Thorbjørn Ravn Andersen
2010-09-27 15:55:22
+3
A:
No, for given examples it would be impossible. Turing completness is about implementing algorightms and such things, it won't tell you if you cant implememnt any software in it. Google depends mostly on their databases which you can't operate directly through JavaScript, ergo no DB == no Google.
Tomasz Kowalczyk
2010-09-11 01:15:17
Good answer. The key point is that Turing Completeness is about computing answers to problems. It says nothing about I/O, storage, interfaces with other software, etc.
Tyler McHenry
2010-09-11 01:20:46
@maniac: yup. Of course, then one might ask if you have "implemented Google", if your software is different (and, for example, doesn't use a database)
jalf
2010-09-11 02:08:21
A:
Beyond questions of I/O performance, there are also questions of execution time. The number of steps required for one Turing-complete machine to perform some task may be hundreds of orders of magnitude longer than the number of steps required for another Turing-complete machine to do the same thing. It is thus entirely possible that one machine might be able to complete in a fraction of a second a task which would keep another machine busy until the end of the universe; if the latter machine were somehow allowed to keep going even after the end of the universe, it might be able to produce an answer, but from a practical standpoint, the latter machine would be incapable of usefully solving the problem despite its Turing completeness.
supercat
2010-09-11 05:17:02