(I've asked a similar question on cstheory stack)
I can't find the reference right now, but I remember about an algorithm that on a non-lazy functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to...
@kaveh Are you sure about the tagging here? The way I understand the algorithm, it is applied on language-level, so process-scheduling and especially operating-systems feel out of place.
(probably not since he has not been in chat, I believe)
@JeffE I responded to you comment but I am not sure I understood it well. If it is not clear we can't discuss here (I don't need to be here, you can respond at any time)
This is halfway a joke question, but I would like to know the answer anyway.
Can iPhone be considered turing complete, if I cannot load my code on it without Apple's approval?
(if this question is completely off for some reason, I would like to know, too)
@Raphael IIRC the mutual exclusion and more generally algorithms related to processes are discussed in operating systems courses extensively, in fact one or more chapters are often devoted to the topic (e.g. cs.vu.nl/~ast/books/mos2)
I think in general PL tag can also be fine for mutual exclusion, and for this question I agree that PL might be more suitable tag. Maybe also parallel-computing tag.
@Raphael in complexity of computing queries in a language.
@Kaveh I don't understand that remark. "Is this in NC?" -- The asker clearly wants parallel time complexity.
@jmad You only get notifications if were in the room recently, so he probably did not get that message. You can always link from the site to your chat messages, though.
@Gilles If that were true, you could not have understood "from being trivial in the presence Turing complete apps," the way you apparently have; if there are no Turing-complete apps (as you say), my statement does not claim anything.
If there are, however, then the iPhone is trivially Turing-complete.
@Raphael In English, "being trivial in the presence [of] Turing complete apps" implies that the answer is trivial, and that the presence of Turing-complete apps is a reason (in the cognitive sense, not in the logical implication sense) for that
@Gilles Well, two non-native should probably not discuss language semantics. You can read it that way (most will) but that's not what is written. The causality is not explicit, but interpreted. Compare "is trivial in the presence..." with "is trivial because of the presence..." -- maybe that's my theory bias, but the first says "presence => trivial" while the second says "trivial /\ presence".
@Raphael asking for complexity of operators in a (relational) database query language is descriptive complexity. In any case I still think the question needs further clarification as I said in my comments under the question.
@Raphael @Gilles I think this is related to the issue of general computability that has been discussed in a number of Ted talks.
I can look it up but it shouldn't be difficult to find. I guess what the OP has heard is related to that.
@Kaveh Not familiar with it. If that is what the OP wants, he should say so. But you could give a nudge. If Gilles is right and the problem is his understanding of Turing completeness, then he might not know what he heard is non-standard.
The point, AIUI, is that Apple puts restrictions on the possible programs that can run on the machine in such a way that the machine cannot act as a general purpose computer for the users.
e.g. any program that would allow users to write Turing complete code is forbidden on their app store
e.g. flash.
there was quite a number of posts about this in the news last year.
it keeps possible misunderstandings about memory and function vs program (but makes them explicit), but allows answers to explore the censoring side as well
I think the OP should clarify the question and provide the context so we know what is being asked exactly in place of guessing :). If the OP edits and clarifies the question then the question can be reopened.
Go ahead, I don't care. You can also let the OP pick.
We have different interpretations of the original question which have both zero evidence because there was nothing in the question. We should not have spent more time on it than closing and requesting more information.
@Raphael let me be clear: if the original question had been your version, I would have edited it or closed it. Quite possibly edited it to something like the original version.
This is halfway a joke question, but I would like to know the answer anyway.
Can iPhone be considered turing complete, if I cannot load my code on it without Apple's approval?
(if this question is completely off for some reason, I would like to know, too)
The question Is iPhone turing complete? was closed. Should it have been?
