I'm using "Turing complete", perhaps incorrectly, in the sense that Larry Wall (inventor of Perl) did in a related article at http://www.perl.com/lpt/a/997, where he says: "Basically, you can say pretty much anything in any human language, if you work at it long enough. Human languages are Turing complete, as it were."
Pirahã seems to be a language where expressing certain kinds of complex ideas doesn't work. Sure, one might say "I saw the dog. The dog is by the river." I'm not sure that's the same as "I saw the dog which bit me while I was down at the river yesterday looking for fresh-water oysters to feed my mother-in-law to impress her because she's telling my wife I'm a loser because my alligator hunting sucks." My impression is it's hard to express the latter thought in the language, even breaking it up into separate sentences, without using recursion, which the language lacks, at some point.
It is not in fact impossible to express that sort of sentence in Piraha. Embedding is accomplished by "noun-ifying" a clause by adding "-sai". The debate is whether or not this suffix represents actual embedding/recusion. This debate has been discussed at length in Language and other sources.
I'm not sure if this applies, but... can't you convert any recursive algorithm into a looping one? In which case iterating over the loop will let you say anything. But this seems to take the metaphor too far :-)
Pirahã seems to be a language where expressing certain kinds of complex ideas doesn't work. Sure, one might say "I saw the dog. The dog is by the river." I'm not sure that's the same as "I saw the dog which bit me while I was down at the river yesterday looking for fresh-water oysters to feed my mother-in-law to impress her because she's telling my wife I'm a loser because my alligator hunting sucks." My impression is it's hard to express the latter thought in the language, even breaking it up into separate sentences, without using recursion, which the language lacks, at some point.