Not that you'd understand any of it without reading SICP.
Name:
Anonymous2007-06-20 5:35 ID:ZZyTsT6W
Bump.
Can someone really explain it to me, enough joking around? From what I understand, something is turing-complete if it is capable of emulating a "universal turing machine", which apparently is a machine which reads instructions (symbols) from an infinitely long strip of tape? These concepts are weird, like, what exactly is it used for? What's the deal with the infinite tape? Argh
Name:
Anonymous2007-06-20 5:52 ID:yjHspzQ1
Well if the tape wasn't long enough to run a program it couldn't run every possible program...so it's infinitly long.
Name:
Anonymous2007-06-20 8:23 ID:3qNDU09W
Basically given any computational system (symbols on tape + turing machine, the C language, lambda calculus, etc) if you can prove that its intractable to bbcode then this suffices to say the language is turing complete.
Also wang tiles might be worth looking up, any turing complete system can be described by an aperiodic wang tiling.
>>6
Perhaps you should've read more than just the first sentence of the Wikipedia article?
In computability theory, an abstract machine or programming language is called Turing complete, Turing equivalent, or (computationally) universal if it has a computational power equivalent to (i.e., capable of emulating) a simplified model of a programmable computer known as the universal Turing machine. Being equivalent to the universal Turing machine essentially means being able to perform any computational task – though it does not mean being able to perform such tasks efficiently, quickly, or easily.
Name:
Anonymous2007-06-21 7:09 ID:Nmbhk5UJ
I just thought of something...
What if there are calculations that can't possibly be performed by a human brain? We would think that our computers could perform any computation that exists because it can perform any computation we can... We wouldn't know no better.
Proof: Were OP not a retard, he would have found the answer by using Google and Wikipedia. Now, suppose that OP could have used the aforementioned tools, but insisted on asking /prog/. That makes him either a troll or an attention whore, both of which are retards. This concludes the proof.