Transformers are being used extensively across several sequence modeling\ntasks. Significant research effort has been devoted to experimentally probe the\ninner workings of Transformers. However, our conceptual and theoretical\nunderstanding of their power and inherent limitations is still nascent. In\nparticular, the roles of various components in Transformers such as positional\nencodings, attention heads, residual connections, and feedforward networks, are\nnot clear. In this paper, we take a step towards answering these questions. We\nanalyze the computational power as captured by Turing-completeness. We first\nprovide an alternate and simpler proof to show that vanilla Transformers are\nTuring-complete and then we prove that Transformers with only positional\nmasking and without any positional encoding are also Turing-complete. We\nfurther analyze the necessity of each component for the Turing-completeness of\nthe network; interestingly, we find that a particular type of residual\nconnection is necessary. We demonstrate the practical implications of our\nresults via experiments on machine translation and synthetic tasks.\n