Timeline for Are there minimum criteria for a programming language being Turing complete?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2020 at 18:09 | history | edited | sepp2k | CC BY-SA 4.0 | added 1 character in body |
| Sep 30, 2016 at 16:16 | comment | added | sepp2k | @aroth I believe that was already mentioned in this comment chain somewhere, but while some sort of jump instruction is required for the language to be Turing complete, that is not sufficient on its own. Also if we're talking about the machine-code level, on many architectures function calls and returns have their own instructions that can't be replaced with a jump (because there's no direct access to the PC register), so gotos and function calls do not and can not compile to the same instruction on those architectures. | |
| Sep 30, 2016 at 3:36 | comment | added | aroth | In practical terms, where function calls and while loops are supported at the language level they're implemented by using a jump or goto instruction at the machine-code level (whether or not the language exposes direct control of that instruction to the programmer). Thus you might view goto as the prerequisite command, where while and function calls are simply programmer-friendly abstractions of goto. Basically, Turing-completeness requires a 'jump' operation, and it makes no difference how that operation gets packaged. | |
| Apr 3, 2012 at 12:40 | comment | added | Joshua Drake | I believe I see your point now. Given that any language must prove itself Turing Complete there is no reasonable way to say: If you do only X you will create a Turing Equivalent language. Thank you. | |
| Apr 3, 2012 at 12:33 | comment | added | sepp2k | @JoshuaDrake I don't think the article is trying to claim that any Turing-complete language needs to have those operations. Especially since it specifically restricts that statement to procedural languages. Except for a form of goto (i.e. function application) the Lambda Calculus doesn't have any of those things. I think "minimum" here only means that in a language that only has those features, you can't remove any of them without losing Turing completeness. Not that there's no other minimal set of operations that is also sufficient for Turing completeness. | |
| Apr 3, 2012 at 12:09 | comment | added | Joshua Drake | I'm still bugged by the wikipedia Turing completeness article stating: <blockquote>at a minimum, conditional branching (e.g., an "if" and "goto" statement) and the ability to change arbitrary memory locations (e.g., having variables)</blockquote> | |
| Apr 3, 2012 at 11:59 | comment | added | sepp2k | ...I don't see a way to (non-meaninglessly) define a type of operation, such that the lambda calculus' abstraction operation fits that definition, any Turing complete language has an operation fitting that definition, and any language that has an operation fitting that definition is Turing complete. | |
| Apr 3, 2012 at 11:57 | comment | added | sepp2k | @JoshuaDrake I don't think using "jump" instead of goto gets us to the point where we can define a sufficient and necessary set of operation. It's probably true that every language would need some sort of jump operation (and if it's only function calls), but I don't think you'll be able to come up with further operations to make it sufficient. For example the lambda calculus has two operations: application (i.e. our jump operation) and abstraction (i.e. creating functions)... | |
| Apr 3, 2012 at 11:47 | comment | added | Joshua Drake | You make the point that some languages support Turing Completeness with goto but that some do not, seemingly claiming that because some use it and some do not that goto then cannot be part of a set of operations required for Turing completeness. My point is that goto is simply a syntactical way of implementing a particular more generic operation, such as a jump. Therefore I believe that if you simply abstracted away from specific control structures you would move closer to a set of operations that would at least point toward Turing Completeness. | |
| Apr 2, 2012 at 21:01 | comment | added | sepp2k | @JoshuaDrake I'm not sure what you mean. I'm not limiting operations to control structures. It's just that I don't talk about any operations that aren't control structures in my counter example because they're not relevant to the example. Actually I do mention "a way to store arbitrary amounts of data" - that's hardly a control structure. | |
| Apr 2, 2012 at 20:52 | comment | added | Joshua Drake | The only part I'm not certain on is your answer to the minimal set of necessary operations. You seem to limit your definition of operations to Control Structures which seems to be a much narrower scope than asked, and beyond your own requirement of not defining them "so vaguely, that [they] become meaningless". | |
| Apr 2, 2012 at 14:06 | history | edited | sepp2k | CC BY-SA 3.0 | added 821 characters in body |
| Apr 2, 2012 at 13:57 | history | answered | sepp2k | CC BY-SA 3.0 |