Re: My Problem | What is right for ...

Kenneth Brody <kenbrody@xxxxxxxxxxx> writes:
WillerZ wrote:

Oliver Wong wrote:
[... C and C++ ...]
Both languages are Turing Complete, meaning essentially any program
you can write in one language, you could also write in the other.

Actually, no implementation of either language is Turing Complete.

A Turing Complete language is one which can simulate the operation of a
turing machine.

A Turing Machine has an infinitely long tape, and can therefore record
an infinite number of things.

In C or C++, everything can be addressed by a void *, and the size of a
void * must be defined (CHAR_BIT * sizeof(void *) bits). Therefore any
implementation of either language is limited to recording a finite
number of things.

Nothing says you can't use virtual memory. While it's true not there
is no such thing as "infinite storage", you can have "arbitrarily large
storage". As long as the hardware and O/S support it, you can use an
arbitrarily large storage device, along with some "bignum" library to
hold the data.

Addressible storage is still limited by the size of void*. Each byte
of each existing object must have a distinct address, and there can be
at most 2**(CHAR_BIT * sizeof void*) such addresses.

Does a Turing machine really need inifite storage, or does it simply
need to never hit either end of the "infinitely long" tape?

If I recall correctly, it really needs unbounded storage -- which can
(theoretically) be obtained in C by using a file.

--
Keith Thompson (The_Other_Keith) kst-u@xxxxxxx <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
--
comp.lang.c.moderated - moderation address: clcm@xxxxxxxxxxxx -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
.

Relevant Pages

  • Re: My Problem | What is right for ...
    ... no implementation of either language is Turing Complete. ... an infinite number of things. ... is no such thing as "infinite storage", ...
    (comp.lang.c.moderated)
  • Re: My Problem | What is right for ...
    ... no implementation of either language is Turing Complete. ... an infinite number of things. ... is no such thing as "infinite storage", ...
    (comp.lang.c.moderated)
  • Re: turing completeness
    ... >> If you can program a Turing machine in the language, ... which requires infinite space and mass, ... Not "infinite", otherwise you have an infinite loop somewhere, and ...
    (comp.programming)
  • Re: infinity
    ... >>> Why are you assuming that there is a longest word in the language? ... >> finite, that means none are infinite, therefore S^L is not infinite either. ... > I am not assuming that there is a longest word. ... > the maximum string length, i.e. the largest finite natural number. ...
    (sci.math)
  • OT: Church-Turing thesis (was Re: TCL cant do as much as Perl)
    ... Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine, thus they are equally powerful, and no language can exist that is more powerful. ... the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". ... An effective method is defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. ...
    (comp.lang.tcl)
Loading