Does turing completeness preclude a language from having a CFG? I couldn't find any paper saying that.
Can a Turing complete language ever have a CFG?
1.1k Views Asked by Bighted19 At
1
There are 1 best solutions below
Related Questions in PARSING
- How to resize images with PHP PARSE SDK
- Constraint not propagated upon instantiation of list members
- How can I parse fixed-length, non-delimited integers with attoparsec?
- jSon result optional value error
- Date parse with Timezone - Android
- URL Variable is not being recognized using NSURL
- Regex to get vCard base64 string (C#)
- Retrieving string value from label and then parsing into an integer, pyqt4
- How to use Papa Parse for javascript csv parsing
- How to parse/split a string?
- String concatenation with padded integers
- Is this file an XML or HTML file? How can I parse it?
- json parser to spinner
- Use DateTime format in a class but restrict time tokens
- Saving multiple occurrences of strstr() from a line in C?
Related Questions in GRAMMAR
- VoiceXML Grammar Input sequence
- Is the grammars in Java7 spec really equivalent?
- int* const* foo(int x); is a valid C function prototype. How do you "read" this return type?
- Identifier terminal except certain keywords
- Grammar: Precedence of grammar alternatives
- Context Free Grammar BNF
- ANTLR4 grammar conflicting rules
- Is it incorrect online version of EBNF standard, or incorrect the chapter's name by mr. Pattis?
- Cross reference to multiple names in the same grammar rule
- Xtext grammar describing cron expression not working as expected
- What are the Bison/yacc grammars for these
- Correct way of conjugating 3rd person singular in comments
- Xtext grammar rule composite
- Trying to find Shift/Reduce conflict in Grammar
- Why do we need the alternative definition `nested-name-specifier identifier ::` in the definition of the grammar production `nested-name-specifier`?
Related Questions in CONTEXT-FREE-GRAMMAR
- Strings from grammar
- Grammar: Precedence of grammar alternatives
- Context Free Grammar BNF
- Xtext grammar describing cron expression not working as expected
- can removing left recursion introduce ambiguity?
- How to match with a expression grammar only the last time a keyword occurs occurs
- This LL(1) parse table is correct?
- syntax-directed definition to determine the type of expression
- Nullable nonterminals
- Is ε terminal in context-free?
- CFG to Regular expression
- How to fix shift-reduce conflict in this grammar
- How to deal with some ambiguous context free grammar productions in Python
- writing a parser in prolog
- How to Generate and display ParseTree for an expression in C# using Irony?
Related Questions in TURING-MACHINES
- Direct Reduction, Turing machine and a DFA
- Is $E_{LBA}$ a Turing recognizable language?
- Is there a way to get an accepted input from a Turing Machine?
- How to simulate f(1^n)=1^y where y=1+2+...n in Turing Machine Simulator?
- What elements does a turing complete programming language need to consist of?
- How do I find largest subsequence in turing?
- Does there exist a TM for all countable languages?
- Showing turing machines exist for the following
- Turing Machines and Lambda Calculus equivalence
- Turing Machine that finds even or odd length
- Is this language decidable, recognizable, or unrecognizable?
- How to convert a DFA to a Turing machine?
- How do I get this section of code to run until the tape is done?
- Number of Turing Machines?
- How is Turing Machine which accepts nothing is not Recursively Enumerable?
Related Questions in TURING-COMPLETE
- Is HTML Turing Complete?
- What is the simplest Turing complete CPU instruction set which can execute code from ROM?
- What elements does a turing complete programming language need to consist of?
- Criteria to determine if it's a programming language
- What logic gates are required for Turing completeness?
- Turing Complete Alphanumeric x86 Instruction Set (Subset)
- Is my program Turing-complete?
- Generally, is it possible to write kinect-like app using only C++?
- Are Perl regexes turing complete?
- Is pure Prolog Turing-complete, and if so, why can't it implement list intersection?
- Would x86 still be fully programmable if it didn't have the Sign Flag (SF)?
- Can a Turing complete language ever have a CFG?
- Is C# 4.0 compile-time turing complete?
- TOC program A that when given any program B as input can determine whether or not B produces “hello world”
- Is bzip2 turing complete?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
We are often imprecise with these terms, but a correct answer to your question requires that we be very precise with how we are using terms.
Two computation systems are equivalent if they can simulate each other. A computation system is Turing-equivalent if it is equivalent to Turing machines.
A computation is complete with respect to a computation system if it requires all capabilities of that system to be computed in that system; that is, any change to the computing system which causes it not to be capable of performing at least the same computations as before will cause it not to be able to perform this computation. A computation is Turing-complete if it is complete with respect to Turing machines.
BNF grammars describe context-free languages, and the least capable computing system capable of parsing such languages are the pushdown automata. This computing system cannot simulate Turing machines in that there are computations a Turing machine can perform which a pushdown automaton cannot; therefore, pushdown automata are not Turing-equivalent.
The article says that TeX is a Turing-complete language, that is, deciding the language of valid TeX strings requires all capabilities of Turing machines. Any system not capable of simulating a Turing machine cannot possibly parse decide membership in the language of valid TeX strings.
The article is NOT saying that TeX is Turing-equivalent (maybe it is, maybe it isn't; I have no idea). As pointed out in the comment, Turing-completeness of a computation system's representation is completely unrelated to that computation system's Turing-equivalence. Even Turing machines themselves can be represented using strings of a regular language (in fact, extend the interpretation of any language so that otherwise invalid programs compile to the program which halts without doing anything, and suddenly ALL strings are valid, and the language of all strings is certainly regular).