Turing completeness
Often I read that an esoteric language is Turing Completeness when it can "simulate any Turing machine and by extension the computational aspects of any possible real-world computer". Ok - I agree, but is there a program which can does the demonstration? Is there a classical code which can (if it can be executed using this language) proves that the used language is Turing Completeness? Do you understand what I mean? Compute the Fibonacci Numbers (just an example) is great, but this is not a clear demonstration that a language is Turing Completeness. I am searching something more relevant. Any comment will be appreciated ++
Last edited on
I do not think this is possible to test for by a computer; I believe it runs into other NP complete problems such as the halting problem (is that the right one?) where you are asking one program to determine if another program can be crashed by some arbitrary input...
But the thing to ask here is 'what can't a turing machine do?'
But the thing to ask here is 'what can't a turing machine do?'
Like jonnin implies, for specific cases, you can just find any Turing-complete system and simulate it in your language of choice. One approach is to write a program that could simulate an arbitrary Turing machine. Or a program which generates strings from an arbitrary phrase structure grammar. If your language can do that it's Turing-complete.
It's impossible to have a decision procedure that says (in general) whether another program simulates a Turing-complete system. All you have to do to prove it is write a second program that simulates a Turing-complete system only if the decision procedure indicates that it doesn't.
PS. NP-complete roughly means "needs exponential time to solve" whereas the halting problem is just impossible.
| Is there a program which can does the demonstration? |
PS. NP-complete roughly means "needs exponential time to solve" whereas the halting problem is just impossible.
Last edited on
Thank you for your comments.
I continue a little bit more further... BrainFuck is one of the most minimalist language which is (as they said) Turing Completeness. I am very impressed by what can be done using only eight commands (or operators). According to its creator and other developers, BF is Turing-Complete. How can they say that? Where is the proof of concept?
https://en.wikipedia.org/wiki/Brainfuck
I continue a little bit more further... BrainFuck is one of the most minimalist language which is (as they said) Turing Completeness. I am very impressed by what can be done using only eight commands (or operators). According to its creator and other developers, BF is Turing-Complete. How can they say that? Where is the proof of concept?
https://en.wikipedia.org/wiki/Brainfuck
Eight is massively over specified :)
Try one.
https://en.wikipedia.org/wiki/One-instruction_set_computer
Try one.
https://en.wikipedia.org/wiki/One-instruction_set_computer
To have Turing-completeness you just need three things:
* The ability to read and write bits on an infinite amount of memory.
* Conditional jumps forward.
* Unconditional jumps backward.
Any language capable of expressing all three things is Turing-complete, because those are the capabilities of the abstract machine Turing defined. As for whether all Turing machines are equivalent, that's the Church-Turing thesis, and there's no proof of it. In fact, as I recall, there can be no proof of it.
By the way, technically speaking no real life implementation of a programming language nor any computer can be Turing-complete. Instead they're pushdown automata, since they're only able to access finite amounts of memory. When talking about real systems the first condition is relaxed to say that it must be able to allocate arbitrary amounts of memory. So for example a language in which you can only declare individual variables would not be Turing-complete in this sense, but one in which you can declare arrays would be.
* The ability to read and write bits on an infinite amount of memory.
* Conditional jumps forward.
* Unconditional jumps backward.
Any language capable of expressing all three things is Turing-complete, because those are the capabilities of the abstract machine Turing defined. As for whether all Turing machines are equivalent, that's the Church-Turing thesis, and there's no proof of it. In fact, as I recall, there can be no proof of it.
By the way, technically speaking no real life implementation of a programming language nor any computer can be Turing-complete. Instead they're pushdown automata, since they're only able to access finite amounts of memory. When talking about real systems the first condition is relaxed to say that it must be able to allocate arbitrary amounts of memory. So for example a language in which you can only declare individual variables would not be Turing-complete in this sense, but one in which you can declare arrays would be.
To have Turing-completeness you just need three things: * The ability to read and write bits on an infinite amount of memory. * Conditional jumps forward. * Unconditional jumps backward. |
Interesting. Do you have a paper or a link about these rules?
Topic archived. No new replies allowed.