Re: Beginner Question(s): Understanding Turing Completeness
- From: torbenm@xxxxxxxxxxxxx (Torben Ægidius Mogensen)
- Date: Wed, 20 Jun 2007 14:18:04 +0200
kilik3000@xxxxxxxxx writes:
I'm having a hard time understanding Turing Completeness. I checked
out the Wikipedia article (http://en.wikipedia.org/wiki/Turing-
complete), but it seems kind of broad.
Does anyone out there have a concise definition for Turing
completeness?
A machine or programming language is Turing-complete if it can compute
the same functions that a Turing-machine can.
Nearly all traditional programming languages are Turing-complete if
you assume unbounded memory.
Why is everybody so concerned about it?
Not all are. But since a lot of results about undecidability
etc. have been proven to apply to all Turing-complete languages and
machines, you can establish a lot of facts about a language or machine
by proving it Turing-complete,
How does it relate to the field of software development?
Not much, except that you can sometimes by deliberately designing a
language to be not Turing complete, you can decide some properties
that are undecidable for Turing-complete languages. So if these
properties are important to you, you can get guarantees that you can't
if you use a Turing-complete language.
Torben
.
- References:
- Beginner Question(s): Understanding Turing Completeness
- From: kilik3000
- Beginner Question(s): Understanding Turing Completeness
- Prev by Date: Beginner Question(s): Understanding Turing Completeness
- Next by Date: Re: A letter want to disprove my paper which submitted recently
- Previous by thread: Beginner Question(s): Understanding Turing Completeness
- Index(es):
Relevant Pages
|
