what can Java do that C/C++ can't?
darkpark
Java. I didn't think that Java has any usefullness especially compared
to C/C++. So what are the advantages of one over the other? Why would
someone choose Java, for example?
Ola Gustafsson
The biggest reason for choosing Java over C/C++ is scope. Java, as a language,
is more high-level than C/C++. There are lots of things that are easier
in Java. For example, working with Sockets.
But C/C++ is always faster. And that's the big tradeoff.
--
Ola Gustafsson
Ron Ruble
"Ola Gustafsson" <Ola.Gus...@itc.ki.se> wrote in message news:u1xzt2...@itc.ki.se...
In the hands of comparably skilled, reasonably talented programmers.
A bad C++ programmer can write a _much_ slower program than
a good Java programmer. _Many_ C++ programmers are not
nearly as talented as they think they are. See CERT for a _long_
list of security defects. While CERT doesn't have information on
what languages were used, it's a fair bet that almost all of the
buffer overflows listed were coded in C or C++, as well as a
significant number of the other security defects.
Java programmers can write bad code, too. It's just that the nature
of the languages encourage different stupidities. C and C++ tend
to attract the "muy macho" types who say "string class? I don't
need no stinkin' string class! I can make it faster with direct use
of character pointers!" *
> And that's the big tradeoff.
There are other tradeoffs, as well. Garbage collection makes memory
use non-deterministic, which can complicate performance planning,
and Java requires a VM, which can complicate deployment.
In answer to the specific question in the subject line, there is _nothing_
Java can do that C++ _can't_. Java may be able to do it more easily,
more safely, more effectively, etc., but Java can't do anything that
can't be coded in C++.
---------------------------
* I use Java _and_ C++, and use C++ much more often. C++ is
fine; it's just not for egomaniacal cowboy coders. If you like, do
a Google search on the phrase "cowboy coders". Several people,
including Larry Constantine, have commented on the joys of
managing these types.
Savio Sena
Consider changing your question to:
``In which cases Java is a better solution to my problem?''
and you will understand that almost every language has its purpose.
btw, C/C++ does not exist.
/savio
--
Savio Sena
Jarra McIntyre
"darkpark" <dark...@nolight.com> wrote in message
news:W7wpa.584214$F1.79873@sccrnsc04...
There is 3 things which Java can do that C++ cannot do:
1. Write Cross Platform compatible code which can be compiled into Cross
Platform compatible binaries and takes advantage of a rich runtime
environment.
2. Full support for multi threading in the language, i.e. syncronized
keyword.
3. Garbage collection integrated into the language, no garbage collection
library written for C++ can integrate with the language the way the Java GC
is integrated.
Of course all of these limitations can be overcome, just with a great deal
of difficulty
Ola Gustafsson
> In the hands of comparably skilled, reasonably talented programmers.
>
> A bad C++ programmer can write a _much_ slower program than
> a good Java programmer. _Many_ C++ programmers are not
> nearly as talented as they think they are. See CERT for a _long_
> list of security defects. While CERT doesn't have information on
> what languages were used, it's a fair bet that almost all of the
> buffer overflows listed were coded in C or C++, as well as a
> significant number of the other security defects.
>
> Java programmers can write bad code, too. It's just that the nature
> of the languages encourage different stupidities. C and C++ tend
> to attract the "muy macho" types who say "string class? I don't
> need no stinkin' string class! I can make it faster with direct use
> of character pointers!" *
Couldn't agree with you more. As you say, buffer overflows are quite unheard
of in the Java-world.
I recognize that "macho"-thinking from my first days programming. When
you are new with a language like C++, all the power is quite overwhelming.
>
> > And that's the big tradeoff.
>
> There are other tradeoffs, as well. Garbage collection makes memory
> use non-deterministic, which can complicate performance planning,
> and Java requires a VM, which can complicate deployment.
Sometimes. But sometimes the VM actually makes things alot easier.
Just an example, porting a GUI-application from Win32 to X11.
The best way I see is to write it in Java from the beginning.
Cheers
--
Ola Gustafsson
CBFalconer
I would say that Java has slightly less insecurities than C or
C++, and has a good possibility of being binary portable to
another system. For the insecurities, Ada is probably better.
For binary portability, I know of nothing **popular** that
competes.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Ron Ruble
"Jarra McIntyre" <jmci...@bigpond.net.au> wrote in message news:%7zpa.8291$8K2....@news-server.bigpond.net.au...
>
<snip>
>
> There is 3 things which Java can do that C++ cannot do:
Not precisely.
> 1. Write Cross Platform compatible code which can be
> compiled into Cross Platform compatible binaries and takes
> advantage of a rich runtime environment.
C++ can do this. It requires additional discipline and
libaries in addition to the standard libraries. It requires
a compiler which targets an independent virtual platform
(as Java does) but C++ can do this.
Your statement might be better rephrased as:
"Java is more platform independent by nature (true of
_many_ higher level languages), and comes with extensive
and powerful standard, platform independent libraries."
C++ is not; the Standards committee deliberately
avoided adding a huge number of features to the
standard library. GUI? Networking? Hell, there isn't
even standard support for reading _directories_.
> 2. Full support for multi threading in the language, i.e.
> syncronized keyword.
Accurate but: what is the _real_ advantage of language
keywords over library support? It's debatable, and much
if the issue comes down to line-drawing. It's possible to
argue that Java's threading support is actually a limitation,
as has been discussed many times in other newsgroups.
I like Java's thread support, but that just tells you my
personal preference, not anything about the language.
> 3. Garbage collection integrated into the language, no
> garbage collection library written for C++ can integrate
> with the language the way the Java GC is integrated.
Again, this doesn't really address a limitation in C++
so much as a different approach. The Java GC has
design limitations and arguably design defects. Integration
is good for people who like what's been integrated; but
what about the people who picked Coke in the Pepsi
Challenge?
It's like the Swiss Army Knife; I don't drink, so what
the hell do I need with a corkscrew anyway?
> Of course all of these limitations can be overcome, just
> with a great deal of difficulty
Good response; my only complaint is that the points you
bring up are arguable. They are much more about personal
values and preferences of programmers than limitations
of C++. Ultimately, to each point you address, C++
can do it; just not necessarily as easily or as well.
Michael Wojcik
comp.lang.*, but I'm sure they don't need more language religious wars.
Try lurking in a Java advocacy group for a while if you must hear more.]
darkpark wrote:
> I didn't think that Java has any usefullness especially compared to
> C/C++. So what are the advantages of one over the other?
Since there's currently no language called "C/C++" (though I believe
someone's working on one - there was a thread about it in comp.lang.c a
while back - and there is a language called "C\C++", but it's not widely
used), Java has the advantage of actually existing.
If you want to know:
1. What can Java do that C or C++ can't?
Nothing. Java, C, and C++ are all Turing-complete, as are FORTRAN,
COBOL, Scheme, Perl, Ruby, probably Unlambda, and possibly Malbolge.
2. What can someone do with Java that they can't do (directly) with C or
C++?
Well, they can compile to Java bytecode; I'm not aware of a C or C++
compiler that generates Java bytecode. (It would be difficult to
produce one, since the generated bytecode would have to implement the C
or C++ virtual machine on top of the Java virtual machine, as the Java
virtual machine doesn't permit various things which are legal in C
and/or C++. But not impossible.)
Java bytecode will run under Java virtual machine implementations, which
are available on many platforms. (Whether a given Java *program* will
run *correctly* under a given JVM is another question.) That is useful
to some people; thus Java is useful to them. For example, if you're
looking to write an applet that can run on most of the web browsers in
use, Java is a better choice than C or C++.
> Why would someone choose Java, for example?
Because they prefer it, perhaps. Because it's mandated for the project
they're working on, perhaps. Because they want to reuse Java code they
already have, perhaps. All the same reasons why someone chooses any
language.
I usually see Java proponents tout as its primary advantages bytecode
portability, safety (runtime verification and a strong type system), and
to a lesser extent other language features like single inheritance and
interfaces. Portability isn't absolute and is more important for some
tasks than others. Safety also isn't absolute - many VM implementations
have had bugs that allowed programs to elevate privileges, and external
influences can sometimes be used against the VM's protection mechanisms.
Language features are largely a matter of taste. Nonetheless, these
are characteristics that distinguish the typical Java implementation
from the typical C or C++ implementation.
In short, Java is not C or C++. Take one of those differences - the
lack of pointers, for example - and with a bit of thought you can
probably come up with some requirements that might make that difference
an advantage. (Different requirements, of course, might make it a
disadvantage.)
--
Michael Wojcik
Micro Focus International
Programmer Dude
> [This thread is OT for comp.programming. ...]
[We're not very rabid about that sort of thing here. If it's vaguely
computer programming related, it's fine with us.]
> Since there's currently no language called "C/C++" ...
Most non-pedantic folks understand the slash means "and/or".[1] There is
sufficient overlap between C and C++ to make it often possible to discuss
them as a collective. [2]
________________________________________________________________________
[1] Note that "and/or" introduces a slight GNU-like recursion problem...
[2] Now THERE'S a thread. What's a good collective noun for programming
languages? A Disk of Languages? A Download of Languages?
--
|_ CJSonnack <Ch...@Sonnack.com> _____________| How's my programming? |
|_ http://www.Sonnack.com/ ___________________| Call: 1-800-DEV-NULL |
|_____________________________________________|_______________________|
Ben Tels
> The other day, I had a debate with a coworker about the usefullness of
> Java.
Oh, one of those.....
> I didn't think that Java has any usefullness especially compared
> to C/C++. So what are the advantages of one over the other? Why would
> someone choose Java, for example?
Someone might choose Java when one wants to use a language that is somewhat
easier to write and read than C or C++, in which it is harder to get lost
in a program. One might also use Java when one wants to use a language that
is targeted at large software projects at the systems level (i.e. not the
sort of thing you'd use a scripting languages for) that avoids some of the
common errors and headaches of C and C++ (buffer overflows, other memory
management issues, multiple inheritance quirks) and that has a large
standard library full of modern facilities (not just math routines like C
and C++ and some containers but also networking, GUI building, database
connectivity, multithreading* and such). Java is also the primary language
for J2EE development plus it has a relatively large foothold on small
devices. And, of course, if you are targeting multiple platforms Java has
the advantage of the JVM platform that abstracts away from such concerns.
The downside to all this is that you'll notice the performance drag of
JVM-based programs (not just Java; many languages' programs can be compiled
onto the JVM, including something approaching C and C++) much faster than
you will when using C or C++ to compile a native program. You can build
performance hogs in both, but it is easier to do in Java -- most programs
require at least some performance tuning in Java, even when you can get
away with a comparable program using almost the same routines written in
C++ (and especially in C). And of course, you cannot target the really low
level -- the hardware -- with Java; Java was designed to target the Java
Virtual Machine, not every which computer that was ever invented. C and C++
on the other hand can be laced with assembly-level instructions and can
therefore be used for driver-level coding, whereas the concept of "driver"
is alien to Java: there's no such thing in a JVM.
Beyond that (if such is your concern), Java is more verbose than C++ and C.
C is an imperative language, C++ is C with objects strapped onto it. Java,
on the other hand, cannot live without classes and objects. This tends to
make Java programs wordy.
* There's even language support for that one.
--
Ben Z. Tels
b...@bentels.dyndns.org
"The Earth is the cradle of the mind, but one cannot stay in the cradle
forever."
--Tsiolkovsky
CBFalconer
>
... snip ...
>
> [2] Now THERE'S a thread. What's a good collective noun for programming
> languages? A Disk of Languages? A Download of Languages?
Murder?
Programmer Dude
>> [2] Now THERE'S a thread. What's a good collective noun for programming
>> languages? A Disk of Languages? A Download of Languages?
>
> Murder?
You think programming languages are like crows? ;-)
Other suggestions (although I'm leaning towards "download" myself):
A Screen of Languages
A Script of Languages
A Compile of Languages
A Core of Languages
Electric Monk
>
> > The other day, I had a debate with a coworker about the usefullness of
> > Java. I didn't think that Java has any usefullness especially
> > compared to C/C++. So what are the advantages of one over the other?
> > Why would someone choose Java, for example?
> >
> The biggest reason for choosing Java over C/C++ is scope. Java, as a
language,
> is more high-level than C/C++. There are lots of things that are easier
> in Java. For example, working with Sockets.
Only because the standard libraries for Java include classes for working
with sockets. There are a number of non-standard libraries for C++ that
provide socket access as good as Java's socket libs, etc. Where do you draw
the line? Are standard libraries considered part of the language itself?
> But C/C++ is always faster. And that's the big tradeoff.
Make that ALMOST always. As a friend of mine pointed out the other day
there are a number of devices now (mobile phones, PDAs, etc) that are built
on a hardware Java Machine. That means that, on those devices, Java runs
faster than C++... and in fact, it may not be possible to target a C++
compiler to that platform.
--
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"
MSCHAEF.COM
Electric Monk <emo...@hotmail.com> wrote:
...
>Make that ALMOST always. As a friend of mine pointed out the other day
>there are a number of devices now (mobile phones, PDAs, etc) that are built
>on a hardware Java Machine. That means that, on those devices, Java runs
>faster than C++... and in fact, it may not be possible to target a C++
>compiler to that platform.
The J2ME JVM's I'm aware of are all coded in C or C++ and are
software-only JVM's. Quite different from the old Java hardware
that Sun once thought was a good idea.
-Mike
--
http://www.mschaef.com
CBFalconer
>
> CBFalconer wrote:
>
> >> [2] Now THERE'S a thread. What's a good collective noun for programming
> >> languages? A Disk of Languages? A Download of Languages?
> >
> > Murder?
>
> You think programming languages are like crows? ;-)
>
> Other suggestions (although I'm leaning towards "download" myself):
>
> A Screen of Languages
> A Script of Languages
> A Compile of Languages
> A Core of Languages
I think languages, including English, are regularly murdered.
Arthur J. O'Dwyer
On Wed, 23 Apr 2003, Michael Wojcik wrote:
>
> If you want to know:
>
> 1. What can Java do that C or C++ can't?
>
> Nothing. Java, C, and C++ are all Turing-complete, as are FORTRAN,
> COBOL, Scheme, Perl, Ruby, probably Unlambda, and possibly Malbolge.
Actually, I never did see a definitive answer (e.g., proof) as to
whether ISO C99 is Turing-complete or not. ;) I've been meaning to
ask some CS professors about the recursion thing...
Seriously, does anyone else want to re-open that discussion?
(See Google's archives of comp.lang.c,
"Turing completion without semicolons?", at
http://groups.google.com/groups?
threadm=171aec1a.0302281431.1dc2756e%40posting.google.com&rnum=1
-Arthur,
opening the can marked 'worms'
jim
> Programmer Dude wrote:
>
>>CBFalconer wrote:
>>
>>
>>>>[2] Now THERE'S a thread. What's a good collective noun for programming
>>>> languages? A Disk of Languages? A Download of Languages?
>>>
>>>Murder?
>>
>>You think programming languages are like crows? ;-)
>>
>>Other suggestions (although I'm leaning towards "download" myself):
>>
>> A Screen of Languages
>> A Script of Languages
>> A Compile of Languages
>> A Core of Languages
>
>
> I think languages, including English, are regularly murdered.
>
Languages come by the bin.
Peter Ammon
> Michael Wojcik wrote:
>
>
>>[This thread is OT for comp.programming. ...]
>
>
> [We're not very rabid about that sort of thing here. If it's vaguely
> computer programming related, it's fine with us.]
>
>
>>Since there's currently no language called "C/C++" ...
>
>
> Most non-pedantic folks understand the slash means "and/or".[1] There is
> sufficient overlap between C and C++ to make it often possible to discuss
> them as a collective. [2]
>
I just wrote a fairly simple benchmark in C (the way it's meant to be
used), C++ (the way it's meant to be used, with the STL), Java, and
Dylan. Java was half as fast as C and twice as fast as C++. This shows
two things:
1) Java isn't always slower than C++
2) It's inappropriate to speak of C and C++ as part of a collective
> ________________________________________________________________________
> [1] Note that "and/or" introduces a slight GNU-like recursion problem...
>
> [2] Now THERE'S a thread. What's a good collective noun for programming
> languages? A Disk of Languages? A Download of Languages?
Hash table.
-Peter
Walter
"Electric Monk" <emo...@hotmail.com> wrote in message
news:10511266...@cereal.attica.net.nz...
> That means that, on those devices, Java runs
> faster than C++... and in fact, it may not be possible to target a C++
> compiler to that platform.
Since JVMs are written in C/C++, clearly it must be possible.
Ola Gustafsson
> Only because the standard libraries for Java include classes for working
> with sockets. There are a number of non-standard libraries for C++ that
> provide socket access as good as Java's socket libs, etc. Where do you draw
> the line? Are standard libraries considered part of the language itself?
I was talking about ease from beginning to end. If you use non-standard libraries
you have to make sure these libraries are available on all places the program
will be used. If you're no sure if they will be, you have to distribute
the library together with your code, etc.
I believe that standard libraries should be considered part of the language
if they always exist on all possible targets for the language.
If you take a Sun certification in Java Programming, you have
to know the standard libraries. This doesn't prove anything of course.
>
> > But C/C++ is always faster. And that's the big tradeoff.
>
> Make that ALMOST always. As a friend of mine pointed out the other day
> there are a number of devices now (mobile phones, PDAs, etc) that are built
> on a hardware Java Machine. That means that, on those devices, Java runs
Of course, it should be almost always. As an earlier post in this thread
prooved, you can write _stupid_ C++-programs which are slower than the
Java counterparts.
I don't know if such devices actually exist, but if they do, you are
correct.
> faster than C++... and in fact, it may not be possible to target a C++
> compiler to that platform.
Well, you would have to build a C++ Virtual Machine. =)
--
Ola Gustafsson
Ola Gustafsson
> I just wrote a fairly simple benchmark in C (the way it's meant to be
> used), C++ (the way it's meant to be used, with the STL), Java, and
> Dylan. Java was half as fast as C and twice as fast as C++. This
> shows two things:
Who are you to say "the way it's meant to be used"? I know of only 2 persons for C
and 1 for C++. But even so, if you got the Java-program to run twice as fast as
C++, I believe you've done something really strange. Used properly, templates,
classes and everything else which is part of C++, a C++ program
runs as fast as a C-program.
> 1) Java isn't always slower than C++
As said above, your test doesn't say anything new. All languages can be abused
to the point of infinity.
The fact remains, Java, C and C++ are for totally different problem domains.
Java is most likely slower in all real world applications, but that
doesn't matter, because it's used in situations where the speed is not
the most important objective.
> 2) It's inappropriate to speak of C and C++ as part of a collective
Why? C++ as backwards-compatible with C. All (or allmost all) legal
C programms are legal C++.
>
> > [2] Now THERE'S a thread. What's a good collective noun for
> > programming
> > languages? A Disk of Languages? A Download of Languages?
>
> Hash table.
I think a Cast of Languages should be appropriate. =)
--
Ola Gustafsson
Jeremy Yallop
> I just wrote a fairly simple benchmark in C (the way it's meant to be
> used), C++ (the way it's meant to be used, with the STL), Java, and
> Dylan. Java was half as fast as C and twice as fast as C++.
Could you post the code?
Jeremy.
Electric Monk
news:ptLpa.328804$OV.363571@rwcrnsc54...
If it's a JVM then sure. I was talking about HARDWARE java machines...
processors for which java bytecode is the native instruction set.
After Mike's reply I did a little digging and failed to turn up any evidence
that these are actually in use. I found several proposals for java
processors, but most of the portable systems that support java do seem to
run a JVM. In that case, targetting the underlying processor with a C++
compiler is obviously an option :)
Electric Monk
> "Electric Monk" <emo...@hotmail.com> writes:
<snip>
>
> > faster than C++... and in fact, it may not be possible to target a C++
> > compiler to that platform.
> Well, you would have to build a C++ Virtual Machine. =)
Ooh... now wouldn't that be fun? :>
Actually it's an interesting thought experiment. I wonder how difficult it
would be to implement a risc-like virtual machine in java?
Electric Monk
news:b87rge$im9$1...@news01.cit.cornell.edu...
<snip>
>
> I just wrote a fairly simple benchmark in C (the way it's meant to be
> used), C++ (the way it's meant to be used, with the STL), Java, and
> Dylan. Java was half as fast as C and twice as fast as C++. This shows
> two things:
>
> 1) Java isn't always slower than C++
> 2) It's inappropriate to speak of C and C++ as part of a collective
First of all, which compiler(s) did you use for the C and C++ programs?
Which STL does your compiler use? Did you do full release builds in all
cases?
Secondly, who says the STL is the way C++ is 'meant to be used'? STL is a
tool, not a requirement.
Ola Gustafsson
> "Ola Gustafsson" <Ola.Gus...@itc.ki.se> wrote in message
> news:uadegv...@itc.ki.se...
> > "Electric Monk" <emo...@hotmail.com> writes:
> <snip>
> >
> > > faster than C++... and in fact, it may not be possible to target a C++
> > > compiler to that platform.
> > Well, you would have to build a C++ Virtual Machine. =)
>
> Ooh... now wouldn't that be fun? :>
>
> Actually it's an interesting thought experiment. I wonder how difficult it
> would be to implement a risc-like virtual machine in java?
Yeah, quite fun =)
I'm far from as good as I should be on the RISC-architecture. But on the
other hand, how hard could it be? =)
--
Ola Gustafsson
Bill Godfrey
> [2] Now THERE'S a thread. What's a good collective noun for programming
> languages? A Disk of Languages? A Download of Languages?
If I understand correctly, human languages use "family" (such as "Roman")
and "super family" (such as "Indo-European").
The "C family" and the "Algol super family" anyone?
Bill, appologies for being serious.
Gerry Quinn
>If it's a JVM then sure. I was talking about HARDWARE java machines...
>processors for which java bytecode is the native instruction set.
>
>After Mike's reply I did a little digging and failed to turn up any evidence
>that these are actually in use. I found several proposals for java
>processors, but most of the portable systems that support java do seem to
>run a JVM. In that case, targetting the underlying processor with a C++
>compiler is obviously an option :)
C++ evolved from C, and C was built to conform to how typical hardware
works. It's hard to see why the basis of physical hardware should be
redesigned to suit a particular computer language - especially one that
will become obsolete like Java [sorry, but Java has far too many flaws
to have any prospect of taking over the world]. Even if the hardware
could be re-designed, it would probably be sub-optimal. It was designed
originally to suit the computer technology of the time, not to suit C.
Gerry Quinn
--
http://bindweed.com
Screensavers, Games, Puzzles
New! Try our innovative Screensaver Manager
Download evaluation versions free - no time limits
Gerry Quinn
>
>Actually, I never did see a definitive answer (e.g., proof) as to
>whether ISO C99 is Turing-complete or not. ;) I've been meaning to
>ask some CS professors about the recursion thing...
>
>Seriously, does anyone else want to re-open that discussion?
I don't know about recursion, but a Turing complete language can handle
integers of arbitrary size, and therefore must access an arbitrary
amount of memory. How can we do this in C?
We can pre-define int to have a length of googolplex bytes, but even a
program based on such ints can be overcome by sufficiently large
numbers.
(You can't say "just use an infinite tape" because the address is then
held in the tape position, and the program is not responsible for it.)
Calum
> used), C++ (the way it's meant to be used, with the STL), Java, and
> Dylan. Java was half as fast as C and twice as fast as C++. This shows
> two things:
This is indeed a curious (and perhaps even anomolous) result. I can
fully believe that C++ without compiler optimizations would be quite
slow, since the libraries do a lot of internal checking and call a lot
of utility functions which can be optimized away and inlined. You did
turn on the -O option didn't you?
And are you really comparing like with like? I mean, did you
malloc()/strdup() your strings in C?
> 1) Java isn't always slower than C++
> 2) It's inappropriate to speak of C and C++ as part of a collective
They are very different languages, and certainly should not be confused.
But I don't think anyone here believes them to be the same to they?
But perhaps it would be more correct to write C++ instead of C/C++,
since obviously C++ programmers can program in a C-style where appropriate.
>> ________________________________________________________________________
>> [1] Note that "and/or" introduces a slight GNU-like recursion problem...
>>
>> [2] Now THERE'S a thread. What's a good collective noun for programming
>> languages? A Disk of Languages? A Download of Languages?
A redundancy? [Of course, which languages are redundant could lead to
an altogether nastier thread]
Calum
darkpark
hence portability isn't important and also for the sake of the
discussion neither is ease of programming.
So far, it seems to me that Java is used for web-based apps since java
code always seems to be compiled at runtime. Of course, I'm sure that
one could write a full application for the above mentioned platform. No?
So what kind of apps would/could someone write with Java? Could someone
write a game in java (performance issues aside)? I mean a decent game
not something cheesy like solitare.
Again, lets be object with personal preferences aside why would a person
choose java? is high-level language (at least higher level than c/c++)
and tranditionally high level languages tend to be a little slower(?).
Or have modern high-level compilers improved drastically that this is no
longer true?
anyway, thank you for all the responses. i ask this because these two
languages seem to be the most popular and i want decide which language
to study since I would like to learn programming. since i'm a complete
newbie, i'm not sure what i would like to program. don't people
typically decide that they will focus on when they code? when one codes
device drivers, for example, one has to know the hardware very well and
be a lot more effecient. it's a differenting coding style depending on
what you're trying to accomplish (ie: basic win32 application, game,
networking utility, multimedia app, etc...).
Ron Ruble
"darkpark" <dark...@nolight.com> wrote in message news:6ARpa.604574$L1.171360@sccrnsc02...
> So far, it seems to me that Java is used for web-based apps since java
> code always seems to be compiled at runtime.
Whether Java code is compiled during execution is implementation-
defined. MS had a JIT compiler that comiled it the first time it
ran, and just ran the compiled program afterward. Other people
do the same, but JIT compilation is not required.
What any of this has to do with whether the app is web-based or
not is beyond me.
> Of course, I'm sure that
> one could write a full application for the above mentioned platform. No?
Yes.
> So what kind of apps would/could someone write with Java?
Any number of them. IDEs, business productivity tools, all
sorts of things.
> Could someone
> write a game in java (performance issues aside)?
Certainly. There are some.
> I mean a decent game not something cheesy like solitare.
Well, that depends on what you mean by a "decent" game,
and what you mean by "cheesy like solitaire".
You could write almost any _kind_ of game. 3D VR
shoot-em-ups and multimedia adventure games are certainly
doable in Java. Performance is not good, normally, but
vertainly nothing these games do is impossible in Java.
Just not fast.
> Again, lets be object with personal preferences aside why would a person
> choose java?
Most of the reasons people choose languages are _not_
objective.
> is high-level language (at least higher level than c/c++)
Yes, according to the normal definitions of "high-level"
> and tranditionally high level languages tend to be a little slower(?).
Not necessarily. High-level languages are more abstract.
Abstractions have to be mapped to implementations.
The speed of the code tends to be tied to the way in which
the abstractions are mapped to implementation.
For example, the Java AWT is an abstraction above the
normal implementations graphics/UI support. One reason
AWT was so slow was that it attempted to force-fit
every different UI into a generic subset. This made it
difficult to use platform-specific features that were much
higher performance.
By contrast, most UI libraries for C and C++ are not that
abstract; they are tied more tightly to the implementation.
This makes them less portable, but muuch faster.
> Or have modern high-level compilers improved drastically that this is no
> longer true?
It was never generally true that high-level means slow.
It has always been true that a specific instance of an
implementation of a program can be tweaked using low-
level tools so that it runs faster. In other words, it is
almost always possible to do low-level performance
tweaks manually, that a compiler won't or can't do
for you.
This has led to the unwarranted conclusion that the way
to increase performance is to throw out the high-level
tools. This often results in applications that run like a
Ferarri in the city -- 90 MPH to the stoplight, wait
5 minutes, 90 MPH to the stoplight, wait 5 minutes....
> anyway, thank you for all the responses. i ask this because these two
> languages seem to be the most popular and i want decide which language
> to study since I would like to learn programming. since i'm a complete
> newbie, i'm not sure what i would like to program.
Concentrate on learning to program well. This skill
is _independent_ of language, and is best learned
using a high-level language.
> don't people
> typically decide that they will focus on when they code?
??
If I understand you correctly, no; typically, good programmers
learn multiple languages. They use the appropriate tool for
the task, rather than trying to pick the ideal tool for every use.
> when one codes
> device drivers, for example, one has to know the hardware very well and
> be a lot more effecient.
One must know _much_ more than just the hardware.
Especially if one wishes to be efficient. Device drivers are
specific to the OS they run under.
> it's a differenting coding style depending on
> what you're trying to accomplish (ie: basic win32 application, game,
> networking utility, multimedia app, etc...).
Yes, there are different coding styles required for
different types of applications. But there are general
principles common to all of them.
Programmer Dude
> I think languages, including English, are regularly murdered.
Hmmm. Murder requires intent. "Languagacide" is perhaps the more
common case. ;-)
Programmer Dude
>> There is sufficient overlap between C and C++ to make it often
>> possible to discuss them as a collective.
>
> I just wrote a fairly simple benchmark in C (the way it's meant to be
> used), C++ (the way it's meant to be used, with the STL),
Oh? Funny. I don't recall Bjarne mentioning that in his book(s).
> [...] This shows two things:
>
> 2) It's inappropriate to speak of C and C++ as part of a collective
Oh? I used a C++ compiler for years although I was writing C programs
(no classes, no STL). This shows one thing: it's often appropriate to
speak of them collectively. As Bjarne says:
"However, C++ supports every programming technique supported by C.
Every C program can be written in essentially the same way in C++
with the same run-time and space efficiency. [...]
"Well written C tends to be legal C++ also. [...]
"C++ is a direct descendant of C that retains almost all of C as
a subset. [...]
"[E]very construct in C has an obvious C++ equivalent."
Can't get much more collective than that! ;-)
Programmer Dude
> I don't know about recursion, but a Turing complete language can handle
> integers of arbitrary size, and therefore must access an arbitrary
> amount of memory. How can we do this in C?
How can we do it with ANY real language (or real hardware)?
Programmer Dude
>>> [2] Now THERE'S a thread. What's a good collective noun for
>>> programming languages?
>
> I think a Cast of Languages should be appropriate. =)
Good one!
Arthur J. O'Dwyer
On Thu, 24 Apr 2003, Programmer Dude wrote:
>
> Gerry Quinn wrote:
> > I don't know about recursion, but a Turing complete language can handle
> > integers of arbitrary size, and therefore must access an arbitrary
> > amount of memory. How can we do this in C?
Recursion. E.g., the following program will double any input number
(expressed in unary notation as a string of 1's, of course):
#include <stdio.h>
int main(void)
{
if (getchar()=='1') { putchar('1'); main(); putchar('1'); }
return 0;
}
and as far as I know, the above program is ISO-conforming.
(And except for the requisite getchar() and putchar() functions,
it is also _strictly_ conforming.)
> How can we do it with ANY real language (or real hardware)?
Real language? Easy. Brainf**k is Turing-complete, if you use the
infinite-tape model. I wouldn't be surprised if there's a standard
for Lisp, and I wouldn't be surprised if the language specified by
*that* standard was provably Turing-complete.
Real hardware? Impossible. Luckily, the ISO standard imposes no
hardware requirements on the C language. :)
(Just to be very clear: we're talking about the minimal C language,
as defined by ISO, and as implemented on the famous "next-generation"
DS9900, a machine with 17-bit chars where malloc() always returns NULL
and fopen() launches nukes.)
-Arthur
Calum
> I just wrote a fairly simple benchmark in C (the way it's meant to be
> used), C++ (the way it's meant to be used, with the STL), Java, and
> Dylan. Java was half as fast as C and twice as fast as C++. This shows
> two things:
Another thing you could have done was call std::vector<>::push_back()
repeatedly, instead of specifying the size of the vector in the
constructor. I really think you should post your benchmark, since at
the moment you have shown that it is possible to write a bad C++
program, which I think most of us knew already.
> 1) Java isn't always slower than C++
Technically, you have shown this. Though I think you have to try quite
hard to make C++ slower than Java.
Gerry Quinn
>
>>
>> Gerry Quinn wrote:
>> > I don't know about recursion, but a Turing complete language can handle
>> > integers of arbitrary size, and therefore must access an arbitrary
>> > amount of memory. How can we do this in C?
>
>Recursion. E.g., the following program will double any input number
>(expressed in unary notation as a string of 1's, of course):
>
>#include <stdio.h>
>int main(void)
>{
> if (getchar()=='1') { putchar('1'); main(); putchar('1'); }
> return 0;
>}
>
>and as far as I know, the above program is ISO-conforming.
>(And except for the requisite getchar() and putchar() functions,
>it is also _strictly_ conforming.)
I expressly ruled out the use of an infinite tape. Since a language
does not have to be Turing complete to operate such a tape, if such a
tape is permitted then debate about whether a language is
Turing-complete or not is quite meaningless.
- Gerry Quinn
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Gerry Quinn wrote:
>
> "Arthur J. O'Dwyer" wrote:
> >On Thu, 24 Apr 2003, Programmer Dude wrote:
> >> Gerry Quinn wrote:
> >> > I don't know about recursion, but a Turing complete language can
> >> > handle integers of arbitrary size, and therefore must access an
> >> > arbitrary amount of memory. How can we do this in C?
> >
> >Recursion. E.g., the following program will double any input number
> >(expressed in unary notation as a string of 1's, of course):
> >
> >#include <stdio.h>
> >int main(void)
> >{
> > if (getchar()=='1') { putchar('1'); main(); putchar('1'); }
> > return 0;
> >}
> >
> >and as far as I know, the above program is ISO-conforming.
> >(And except for the requisite getchar() and putchar() functions,
> >it is also _strictly_ conforming.)
>
> I expressly ruled out the use of an infinite tape.
Good for you. Where in the above program did I use an infinite tape?
> Since a language
> does not have to be Turing complete to operate such a tape, if such a
> tape is permitted then debate about whether a language is
> Turing-complete or not is quite meaningless.
No. Consider your statement:
Set T: all languages that are Turing complete.
Set X: all languages that operate an infinite tape.
You wrote: A language does not have to be in T in order to be in X.
Thus, if a language is in X, then debate about whether it is in T
is quite meaningless.
As you should be able to see, the question is not answered one way or
another. There are Turing-complete languages with tapes and without
tapes; and there are non-Turing-complete languages with tapes and
without tapes.
C does not have the "tape" abstraction. Is C Turing-complete?
-Arthur
Programmer Dude
>>> I don't know about recursion, but a Turing complete language can handle
>>> integers of arbitrary size, and therefore must access an arbitrary
>>> amount of memory. How can we do this in C?
>>
>> How can we do it with ANY real language (or real hardware)?
>
> A language based on ints of indefinite size should be okay (of course
> there is no prospect of it running on real hardware).
>
> The problem with C is that all structures have a finite, defined size.
> As I see it, that means that C cannot be Turing-complete.
But it allows user-defined types that could be as indefinite as any
other language could support. Do the data types need to be native to
the language for the language to be Turing Complete?
Gerry Quinn
>On Fri, 25 Apr 2003, Gerry Quinn wrote:
>> >Recursion. E.g., the following program will double any input number
>> >(expressed in unary notation as a string of 1's, of course):
>> >
>> >#include <stdio.h>
>> >int main(void)
>> >{
>> > if (getchar()=='1') { putchar('1'); main(); putchar('1'); }
>> > return 0;
>> >}
>> >
>> >and as far as I know, the above program is ISO-conforming.
>> >(And except for the requisite getchar() and putchar() functions,
>> >it is also _strictly_ conforming.)
>>
>> I expressly ruled out the use of an infinite tape.
>
>Good for you. Where in the above program did I use an infinite tape?
Since you implied that your program would work, the existence of a
persistent infinite one-dimensional data store may be deduced. Your
program (and similar ones) won't work without such a structure.
>> Since a language
>> does not have to be Turing complete to operate such a tape, if such a
>> tape is permitted then debate about whether a language is
>> Turing-complete or not is quite meaningless.
>
>No. Consider your statement:
>
> Set T: all languages that are Turing complete.
> Set X: all languages that operate an infinite tape.
>
>You wrote: A language does not have to be in T in order to be in X.
>Thus, if a language is in X, then debate about whether it is in T
>is quite meaningless.
Your syllogism may represent the literal sense of what I wrote, but does
not represent the meaning you should have taken from it. What I meant
(to spell it out) is that there are two sets:
Set T: all languages that are Turing complete
Set Y: all languages that can operate the non-tape part of a Turing
machine, and thus can operate as a Turing machine when a tape is
incorporated.
Set Z: all languages too trivial to do much of interest.
What I proposed, then, is that since Set Y includes both members of T
and members of Z, it provides a poor substitute for categorisations that
should approximate T.
>As you should be able to see, the question is not answered one way or
>another. There are Turing-complete languages with tapes and without
>tapes; and there are non-Turing-complete languages with tapes and
>without tapes.
No language has a tape. A tape is hardware. There may be languages
with a tape abstraction, but C is not one.
>C does not have the "tape" abstraction. Is C Turing-complete?
C is not Turing complete, as far as I can see. (It does fall in the
category of general-purpose languages that is often loosely or
mistakenly referred to as Turing-complete, but it seems to fail because
of the absence of a way to define infinite data structures.)
Gerry Quinn
>Gerry Quinn wrote:
>
>>>> I don't know about recursion, but a Turing complete language can handle
>>>> integers of arbitrary size, and therefore must access an arbitrary
>>>> amount of memory. How can we do this in C?
>>>
>>> How can we do it with ANY real language (or real hardware)?
>>
>> A language based on ints of indefinite size should be okay (of course
>> there is no prospect of it running on real hardware).
>>
>> The problem with C is that all structures have a finite, defined size.
>> As I see it, that means that C cannot be Turing-complete.
>
>But it allows user-defined types that could be as indefinite as any
>other language could support. Do the data types need to be native to
>the language for the language to be Turing Complete?
No, but they have to be defined in an #include file. If you can define
an infinite integer based on the finite types of C, then I take back my
assertion that C is not Turing-complete.
It's very easy, by the way, to define arbitrarily large types. But you
can't define infinite ones, i.e. types larger than *any* arbitrary size.
Come to think of it, C could be used recursively to write and compile C
programs defining increasingly large integral types. That could
represent any problem, I think, but I don't think the recusive
compilation can be considered part of the language.
Robert STRANDH
> Oh? I used a C++ compiler for years although I was writing C programs
> (no classes, no STL). This shows one thing: it's often appropriate to
> speak of them collectively.
It does not show that at all. It shows that you are willing to alter
the idioms of the C language to satisfy the type system and the
semantics of a different language. I think that is a bad idea in
general.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Gerry Quinn wrote:
>
> "Arthur J. O'Dwyer" <a...@andrew.cmu.edu> wrote:
> >On Fri, 25 Apr 2003, Gerry Quinn wrote:
> >> >Recursion. E.g., the following program will double any input number
> >> >(expressed in unary notation as a string of 1's, of course):
> >> >
> >> >#include <stdio.h>
> >> >int main(void)
> >> >{
> >> > if (getchar()=='1') { putchar('1'); main(); putchar('1'); }
> >> > return 0;
> >> >}
> >> >
> >> >and as far as I know, the above program is ISO-conforming.
> >> >(And except for the requisite getchar() and putchar() functions,
> >> >it is also _strictly_ conforming.)
> >>
> >> I expressly ruled out the use of an infinite tape.
> >
> >Good for you. Where in the above program did I use an infinite tape?
>
> Since you implied that your program would work, the existence of a
> persistent infinite one-dimensional data store may be deduced. Your
> program (and similar ones) won't work without such a structure.
Okay. Still, the question wasn't whether a language *without* any
arbitrarily large store could be Turing-complete. I asked specifically
about the *C* programming language. As you seem to be beginning to
grasp, the question is a bit more complicated than it seems at first.
[snip syllogism]
> Your syllogism may represent the literal sense of what I wrote, but does
> not represent the meaning you should have taken from it. What I meant
> (to spell it out) is that there are two sets:
>
> Set T: all languages that are Turing complete
> Set Y: all languages that can operate the non-tape part of a Turing
> machine, and thus can operate as a Turing machine when a tape is
> incorporated.
> Set Z: all languages too trivial to do much of interest.
>
> What I proposed, then, is that since Set Y includes both members of T
> and members of Z, it provides a poor substitute for categorisations that
> should approximate T.
Okay. I still fail to see your point, re: the Turing-completeness of C.
C doesn't have a "tape", nor would there be much point in trying to
"incorporate" one.
> >As you should be able to see, the question is not answered one way or
> >another. There are Turing-complete languages with tapes and without
> >tapes; and there are non-Turing-complete languages with tapes and
> >without tapes.
>
> No language has a tape. A tape is hardware. There may be languages
> with a tape abstraction, but C is not one.
There are languages with tape abstractions, yes.
> >C does not have the "tape" abstraction. Is C Turing-complete?
>
> C is not Turing complete, as far as I can see. (It does fall in the
> category of general-purpose languages that is often loosely or
> mistakenly referred to as Turing-complete, but it seems to fail because
> of the absence of a way to define infinite data structures.)
Which brings us back to (almost) as far as this discussion got in its
previous incarnation. Let's try again. I'll state a theoretical
puzzle, and you try to solve it.
Given a language with global variables, globally defined functions,
function-local variables, and pass-by- both -value and -reference,
and given that all functions can be called recursively, show either:
(a) the language can compute all Turing-computable tasks, or
(b) there exists a Turing-computable task which the language
cannot compute.
Obviously, one Turing-computable task would be the simulation of a
universal Turing machine; but remember, you'd have to prove that the
specified language *cannot* simulate such a machine in order to show
that it's *not* Turing-complete.
Hope this clarifies the puzzle a bit,
-Arthur
Programmer Dude
>> Oh? I used a C++ compiler for years although I was writing C programs
>> (no classes, no STL). This shows one thing: it's often appropriate to
>> speak of them collectively.
>
> It does not show that at all. It shows that you are willing to alter
> the idioms of the C language to satisfy the type system and the
> semantics of a different language.
Nonsense. It's just using a subset of the language. To quote the guy
what gave the language birth:
"Well written C tends to be legal C++ also. [...]
"C++ is a direct descendant of C that retains almost all
of C as a subset. [...]
"[E]very construct in C has an obvious C++ equivalent."
Good enough for me! ;-)
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Programmer Dude wrote:
>
> Robert STRANDH wrote:
[ >someone else wrote:]
> >> Oh? I used a C++ compiler for years although I was writing C programs
> >> (no classes, no STL). This shows one thing: it's often appropriate to
> >> speak of them collectively.
> >
> > It does not show that at all. It shows that you are willing to alter
> > the idioms of the C language to satisfy the type system and the
> > semantics of a different language.
>
> Nonsense. It's just using a subset of the language. To quote the guy
> what gave the language birth:
>
> "Well written C tends to be legal C++ also. [...]
Incorrect in certain aspects, and completely misguided in intent.
Well-written C does not use casts on conversions to or from (void *),
for example. And well-written C is practically never _well-written_
C++; it uses malloc() and free() for memory management, for example,
and eschews // full-line comments. Not to mention the incompatibilities
between C header files (e.g., <stdio.h>) and C++ header files (e.g.,
<cstdio> or (better) <iostream>).
> "C++ is a direct descendant of C that retains almost all
> of C as a subset. [...]
For "C", read "C89". And for "almost all" read "ALMOST all".
> "[E]very construct in C has an obvious C++ equivalent."
This can be said about practically any language in the Algol family.
> Good enough for me! ;-)
And for many people. But then a fork makes a decent hair comb, too.
-Arthur
Ben Tels
> Actually, I never did see a definitive answer (e.g., proof) as to
> whether ISO C99 is Turing-complete or not. ;)
Easy: if it contains the concept of a data store and a way of changing the
contents of one datum in that store, a repetition and a selection
mechanism, it's Turing-complete. Specifically, you can implement a Turing
machine with it (more or less -- you don't have an infinite tape, but most
Turing algorithms don't actually use that infinity).
> I've been meaning to
> ask some CS professors about the recursion thing...
What about recursion?
--
Ben Z. Tels
b...@bentels.dyndns.org
"The Earth is the cradle of the mind, but one cannot stay in the cradle
forever."
--Tsiolkovsky
Ben Tels
> I don't know about recursion, but a Turing complete language can handle
> integers of arbitrary size, and therefore must access an arbitrary
> amount of memory. How can we do this in C?
A Turing machine has no concept of integers. Or numbers of any kind. It's
got an alphabet, nothing more.
Programmer Dude
>>> The problem with C is that all structures have a finite, defined size.
>>> As I see it, that means that C cannot be Turing-complete.
>>
>> But it allows user-defined types that could be as indefinite as any
>> other language could support. Do the data types need to be native to
>> the language for the language to be Turing Complete?
>
> No, but they have to be defined in an #include file. If you can define
> an infinite integer based on the finite types of C, then I take back my
> assertion that C is not Turing-complete.
Can any language define an infinite integer? I'm not familiar with Lisp
(often touted as a definitely T/C language), but in Smalltalk, for instance,
the BigInteger is a class, not a native type. Is Smalltalk T/C?
> It's very easy, by the way, to define arbitrarily large types. But you
> can't define infinite ones, i.e. types larger than *any* arbitrary size.
Can any language? What you can do is define a type+code (a class in an
OOPL) that can embody as many digits as required (limited to hardware).
I can even imagine a ADT that is not limited by pointer sizes and such.
So my question is, does T/C imply *native* to the language, or are you
allowed to construct something?
Programmer Dude
>> "Well written C tends to be legal C++ also. [...]
>
> Incorrect in certain aspects, and completely misguided in intent.
So argue with Bjarne Stroustrup. They're his words. ;-)
> Well-written C does not use casts on conversions to or from (void *),
> for example.
That's an opinion, not a fact. Another opinion is that well-written C
doesn't use void* much (if at all).
> And well-written C is practically never _well-written_ C++;
No one said it was.
> and eschews // full-line comments.
Not since C99.
> Not to mention the incompatibilities between C header files (e.g.,
> <stdio.h>) and C++ header files (e.g., <cstdio> or (better) <iostream>).
Library details.
>> "[E]very construct in C has an obvious C++ equivalent."
>
> This can be said about practically any language in the Algol family.
But how many of them can be compiled by a C++ compiler?
Robert STRANDH
> > Well-written C does not use casts on conversions to or from (void *),
> > for example.
>
> That's an opinion, not a fact. Another opinion is that well-written C
> doesn't use void* much (if at all).
Look, Dude,
You seem to be very opinionated, but in fact you are mostly wrong. If
I were you, I would listen to and learn from people like Arthur here
instead of assuming that you are always right.
Why would you use explicit casts when they are not necessary? Doing
so can hide subtle bugs. Do you also put in explicit casts from
integers to floats? How about from chars to integers?
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Programmer Dude wrote:
>
> >> "Well written C tends to be legal C++ also. [...]
> >
> > Incorrect in certain aspects, and completely misguided in intent.
>
> So argue with Bjarne Stroustrup. They're his words. ;-)
I know. I *was* arguing with Stroustrup. :)
> > Well-written C does not use casts on conversions to or from (void *),
> > for example.
>
> That's an opinion, not a fact. Another opinion is that well-written C
> doesn't use void* much (if at all).
In certain domains that is difficult, if not impossible. But you
probably knew that already.
> > And well-written C is practically never _well-written_ C++
...
> > and eschews // full-line comments.
>
> Not since C99.
_Well-written_ C _still_ eschews // comments, IMHO. Well-written C
tries to avoid most of C99's new features as much as possible, to
maintain backwards compatibility.
I think we both know how things stand between C and C++; there are
substantial similarities and substantial differences. Most of the
differences are due to C++'s OO features; some of the differences
are due to the different syntax and semantics of the two languages.
-Arthur
Bonus puzzle: How many lines of code must you change to make
this C code into a valid C++ translation unit? How many more must
you change to make it a well-written C++ program? Well-written C?
#include <string.h>
#include <stdlib.h>
int handle_string();
handle_string(void *bar)
{
char *old = bar;
char *new = malloc(strlen(old));
strcpy(old, new);
return 0;
}
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Ben Tels wrote:
>
> Arthur J. O'Dwyer wrote:
> > Actually, I never did see a definitive answer (e.g., proof) as to
> > whether ISO C99 is Turing-complete or not. ;)
>
> Easy: if it contains the concept of a data store and a way of changing the
> contents of one datum in that store, a repetition and a selection
> mechanism, it's Turing-complete. Specifically, you can implement a Turing
> machine with it (more or less -- you don't have an infinite tape, but most
> Turing algorithms don't actually use that infinity).
By my definition, a Turing machine *must* be able to simulate an infinite
(i.e., arbitrarily large and unbounded) tape. (This definition is *not*
up for discussion in this thread. I realize that if you ask two people
what a Turing machine is, you'll get three different answers.)
The question is: How do you simulate such a "tape" (or other equivalent
storage device) using ISO C?
> > I've been meaning to
> > ask some CS professors about the recursion thing...
>
> What about recursion?
Read the other branch of this thread, in which I demonstrate how to
double a given number using recursion in C. The question is whether
this method could be expanded to actually simulate a full Turing
machine somehow. I don't immediately see how, but neither do I see
why it would be impossible. The "recursion thing" was mentioned in
the original c.l.c discussion, but it's more of a general computation
puzzle, which is why I thought this newsgroup might have more to say.
We'll find out, I guess.
-Arthur
Ben Tels
> So my question is, does T/C imply *native* to the language, or are you
> allowed to construct something?
You are allowed to construct anything you like.
Programmer Dude
>> Another opinion is that well-written C doesn't use void* much (if
>> at all).
>
> In certain domains that is difficult, if not impossible. But you
> probably knew that already.
In certain domains, yes. In domains I can control, a lot less so.
>>> And well-written C [...] eschews // full-line comments.
>>
>> Not since C99.
>
> _Well-written_ C _still_ eschews // comments, IMHO.
Well, as long as you recognize it as your opinion, cool!
> Well-written C tries to avoid most of C99's new features as much
> as possible, to maintain backwards compatibility.
Yes. If that's important to a project, it would be a good idea.
It HASN'T been important on any project I've done in a long time.
> I think we both know how things stand between C and C++; there are
> substantial similarities and substantial differences. Most of the
> differences are due to C++'s OO features;
Well, yes. The major substantial differences are between what C++
adds to the "C/C++ subset". The differences C has to this subset
are not what *I'd* call substantial. Many of them are trivial.
> Bonus puzzle: How many lines of code must you change to make
> this C code into a valid C++ translation unit? How many more must
> you change to make it a well-written C++ program? Well-written C?
>
> #include <string.h>
> #include <stdlib.h>
> int handle_string();
>
> handle_string(void *bar)
> {
> char *old = bar;
> char *new = malloc(strlen(old));
> strcpy(old, new);
> return 0;
> }
This compiles fine as C/C++ (but it's crappy C or C++):
================================================================
#include <string.h>
#include <stdlib.h>
int handle_string();
handle_string (void *bar)
{
char* old = (char*) bar;
char* New = (char*) malloc (strlen(old)); // <- intentional bug?
strcpy (old, New); // <- intentional bug?
return 0;
}
================================================================
But hate to run it, and I'd be inclined to write it (as C/C++):
================================================================
#include <stdlib.h>
#include <string.h>
int handle_string (void *Bar)
{
char* Old = (char*) Bar;
char* New = (char*) malloc (1+strlen(Old));
strcpy (New, Old);
return 0;
}
================================================================
Or better yet (still a C/C++ program!):
================================================================
#include <stdlib.h>
#include <string.h>
int handle_string (const char Bar[])
{
size_t Len = strlen(Bar) + 1;
char* New = (char*) malloc (Len);
memcpy (New, Bar, Len);
return 0;
}
================================================================
Or as a C++ program:
================================================================
#include <stdlib.h>
#include <string.h>
int handle_string (const char Bar[])
{
size_t Len = strlen(Bar) + 1;
char* New = new char[Len];
memcpy (New, Bar, Len);
return 0;
}
================================================================
You could use <string>, but I don't really like the STL. Too
much overhead for what I usually want to do.
Programmer Dude
>>> Well-written C does not use casts on conversions to or from (void *),
>>> for example.
>>
>> That's an opinion, not a fact. Another opinion is that well-written C
>> doesn't use void* much (if at all).
>
> Look, Dude,
That's Mr. Dude to you.
> You seem to be very opinionated, but in fact you are mostly wrong. If
> I were you, I would listen to and learn from people like Arthur here
> instead of assuming that you are always right.
I never assume I'm right. But when people attack me personally rather
than discuss the issues, heck, I figure I'm on the right track! ;-)
> Why would you use explicit casts when they are not necessary?
Documentation. And to make C code compatible with C++ compilers.
> Doing so can hide subtle bugs.
Hasn't been a problem in the 18 or so years I've been using C.
Hey, maybe you should be listening to and learning from ME! ;-|
> Do you also put in explicit casts from integers to floats?
You bet. To document the format conversion if for no other reason.
I tend to code very explicitly and rarely, if ever, allow silent
default behaviors. (For example, I've NEVER used implicit ints.)
> How about from chars to integers?
Sometimes (see above).
The reality of the matter is that I design code such that casts, in
general, are not necessary. I also tend to treat warning as errors
(in fact, in release builds, warnings ARE errors and break the build).
Programmer Dude
>> So my question is, does T/C imply *native* to the language, or are you
>> allowed to construct something?
>
> You are allowed to construct anything you like.
In that case, what would make C less T/C than any other language?
If you could use C to build a compiler, interpreter or emulator for
an acknowledged T/C language (e.g. Lisp?), isn't C T/C also?
Ben Tels
> By my definition, a Turing machine *must* be able to simulate an infinite
> (i.e., arbitrarily large and unbounded) tape. (This definition is *not*
> up for discussion in this thread. I realize that if you ask two people
> what a Turing machine is, you'll get three different answers.)
Why? A Turing machine never simulates an infinite tape -- the tape is a
thing that the Turing machine has available as a store. In fact, I'm pretty
sure that "simulating" an infinite tape doesn't really mean anything; it's
not something you immitate, it just is. When you talk about Turing
completeness, you're talking about the expressive power of a Turing
machine. In that sense, the fact that you can simulate a Turing machine
with a language that has the concept of store, selection and repetition
makes for Turing completeness.
You have a point in saying that the store of a computer is not as infinite
as that of a Turing machine. However, that in itself does not limit the
nature of expressiveness, only the size of the input and by consequence the
room for the machine to calculate in -- the actions undertaken by the
machine themselves lie in its ability to change the value of a store cell
based on the machine state. As for infinity, no Turing calculation ever
uses that; a calculation that uses infinite space by its nature does not
end in finite time, making the problem undecidable. So that is not a factor
in expressiveness either (the reason the tape is infinite, in fact, is so
that the problem of tape size will not occur).
> The question is: How do you simulate such a "tape" (or other equivalent
> storage device) using ISO C?
You don't -- you don't have to. ISO C, like most programming languages,
doesn't make any assumptions about store size and can address all of the
store. The limited store size lives in the underlying hardware, not in the
language itself. And, like with a "real" Turing machine, this does not
affect the expressiveness, only the size of the input and subsequent
calculation.
> Read the other branch of this thread, in which I demonstrate how to
> double a given number using recursion in C. The question is whether
> this method could be expanded to actually simulate a full Turing
> machine somehow.
Undoubtedly. Recursion as a form of function application is the basis of
lambda calculus, which is equivalent to Turing machines. As for your method
of doubling the ones, sure, you can generate a large number of alphabet
characters that way. But it doesn't mean anything -- you're not writing
your characters back into the store where they can be reused as input but
rather out of the machine into a printer. That will definitely hamper
Turing algorithms that require the ability to reread their own output.
> I don't immediately see how, but neither do I see
> why it would be impossible.
Perhaps not impossible, but it will certainly lock out a class of
algorithms.
Ben Tels
> In that case, what would make C less T/C than any other language?
Nothing -- whether or not C is Turing complete itself, it is at least
equally as expressive as any other language with similar facilities. The
only question here is whether or not C is Turing complete.
> If you could use C to build a compiler, interpreter or emulator for
> an acknowledged T/C language (e.g. Lisp?), isn't C T/C also?
Yes, it is.
Robert STRANDH
Programmer Dude <cjso...@mmm.com> writes:
> > You seem to be very opinionated, but in fact you are mostly wrong. If
> > I were you, I would listen to and learn from people like Arthur here
> > instead of assuming that you are always right.
>
> I never assume I'm right. But when people attack me personally rather
> than discuss the issues, heck, I figure I'm on the right track! ;-)
>
>
> > Why would you use explicit casts when they are not necessary?
>
> Documentation. And to make C code compatible with C++ compilers.
That's what's known as a circular argument: You claim that C is a
subset of C++, because you are able to compile your C programs on a
C++ compiler. Then you say you alter your C programs in ways that are
not considered good style because you want them to compile on a C++
compiler.
In fact, you have altered your C program so that it will fit with the
type system and semantics of C++.
> > Doing so can hide subtle bugs.
>
> Hasn't been a problem in the 18 or so years I've been using C.
> Hey, maybe you should be listening to and learning from ME! ;-|
>
> > Do you also put in explicit casts from integers to floats?
>
> You bet. To document the format conversion if for no other reason.
> I tend to code very explicitly and rarely, if ever, allow silent
> default behaviors. (For example, I've NEVER used implicit ints.)
>
> > How about from chars to integers?
>
> Sometimes (see above).
I have never seen a C program written by an expert that systematically
uses explicit casts between ints on the one hand and chars, unsigned
ints, longs, etc on the other.
> The reality of the matter is that I design code such that casts, in
> general, are not necessary.
That would be VERY hard in C. For instance you could not add 1 to a
char or an unsigned int or a short without either relying on implicit
type conversion or using a cast.
You could also not use getchar() and friends to read characters.
> I also tend to treat warning as errors
> (in fact, in release builds, warnings ARE errors and break the build).
That's good. But the compiler should not give a warning for type
conversions that are valid and common such as assigning a pointer from
a void *.
Arthur J. O'Dwyer
On Fri, 25 Apr 2003, Programmer Dude wrote:
>
> > Bonus puzzle: How many lines of code must you change to make
> > this C code into a valid C++ translation unit? How many more must
> > you change to make it a well-written C++ program? Well-written C?
Well, here's what I'd been thinking when I wrote it down:
> > #include <string.h>
> > #include <stdlib.h>
Obsolete and deprecated C++ headers.
> > int handle_string();
In C++, this declaration prototypes a function which is not
the function below. Unfortunately, I'd forgotten completely
about overloading, so rather than this being a compilation
error in C++, it's merely an extern function declaration.
Still, should be fixed in order to be equivalent to the C.
> > handle_string(void *bar)
Implicit int is no longer supported in C99, and I thought
it wasn't supported by C++ either. But if you say this
line compiles, then I guess I was wrong.
> > {
> > char *old = bar;
Requires a cast in C++. Accepted practice in c.l.c is to
leave off the unnecessary cast in C.
> > char *new = malloc(strlen(old));
> > strcpy(old, new);
As you point out, this is a bug in both C and C++. Whoops.
But also note that <cstring> defines strcpy() in the std::
namespace, and likewise for malloc() and strlen().
And, of course, I was hoping you'd be inclined (as I would)
to use std::string and new/delete in C++.
That's the end of my contribution to this subthread.
-Arthur
Arthur J. O'Dwyer
On Sat, 26 Apr 2003, Ben Tels wrote:
>
> Arthur J. O'Dwyer wrote:
> > By my definition, a Turing machine *must* be able to simulate an infinite
> > (i.e., arbitrarily large and unbounded) tape. (This definition is *not*
> > up for discussion in this thread. I realize that if you ask two people
> > what a Turing machine is, you'll get three different answers.)
>
> Why? A Turing machine never simulates an infinite tape -- the tape is a
> thing that the Turing machine has available as a store. In fact, I'm pretty
> sure that "simulating" an infinite tape doesn't really mean anything; it's
*Having* such a tape is the best simulation of such a tape that I can
think of. But (you know) you can simulate a infinite tape with two
pushdown stacks, or a single tape with only one "infinite end," or an
infinite two-D grid, or lots of other stuff.
> When you talk about Turing
> completeness, you're talking about the expressive power of a Turing
> machine. In that sense, the fact that you can simulate a Turing machine
> with a language that has the concept of store, selection and repetition
> makes for Turing completeness.
> You have a point in saying that the store of a computer is not as infinite
> as that of a Turing machine.
"As infinite"? Any real computer *is* *not* infinite. There's no degree
of comparison involved.
> However, that in itself does not limit the
> nature of expressiveness, only the size of the input and by consequence the
> room for the machine to calculate in --
If my computer can calculate the factorial of ten million, but not the
factorial of ten million million million, then that is a limit on my
computer's "expressiveness." My (real) computer is not T/C, because the
T/C problem "Calculate ten million million million factorial." is not
solvable by my (real) computer.
> the actions undertaken by the
> machine themselves lie in its ability to change the value of a store cell
> based on the machine state. As for infinity, no Turing calculation ever
> uses that; a calculation that uses infinite space by its nature does not
> end in finite time, making the problem undecidable. So that is not a factor
> in expressiveness either (the reason the tape is infinite, in fact, is so
> that the problem of tape size will not occur).
The idea of the infinite tape is so that I can ask my Turing machine,
"What is ten million factorial?" and get an answer in finite time; then
I can ask "What is <that> factorial?" "What is <that> factorial?" ...
and never worry about "running out" of storage. So while no *one*
algorithm needs infinite space, there are *classes* of algorithms that
need *unbounded* space. And a T/C computer must be able to deal with
those.
> > The question is: How do you simulate such a "tape" (or other equivalent
> > storage device) using ISO C?
>
> You don't -- you don't have to. ISO C, like most programming languages,
> doesn't make any assumptions about store size and can address all of the
> store. The limited store size lives in the underlying hardware, not in the
> language itself.
Wrong! The language specified by ISO contains clauses like the following:
7.20.3.3 The malloc function
[...]
[#3] The malloc function returns either a null pointer or a
pointer to the allocated space.
In other words, a strictly conforming ISO C program can't use malloc()
to get more memory when it needs it, because malloc() may return a null
pointer. As regards the size of static objects, consider
7.18.3 Limits of other integer types
[...]
[#2] Each instance of these macros shall be replaced by a
constant expression suitable for use in #if preprocessing
directives, and this expression shall have the same type as
would an expression that is an object of the corresponding
type converted according to the integer promotions. Its
implementation-defined value shall be equal to or greater in
magnitude (absolute value) than the corresponding value
given below, with the same sign.
-- limits of ptrdiff_t
PTRDIFF_MIN -65535
PTRDIFF_MAX +65535
In other words, a strictly conforming ISO C program cannot rely on
being able to define or access arrays of more than 65534 bytes.
> And, like with a "real" Turing machine, this does not
> affect the expressiveness, only the size of the input and subsequent
> calculation.
Right. So the question remains: What is C's "expressiveness" to begin
with? Obviously, adding more capabilities (a typical malloc()
implementation, large objects on the stack) would not make C any more
expressive; so how expressive is ISO C right now?
> > Read the other branch of this thread, in which I demonstrate how to
> > double a given number using recursion in C. The question is whether
> > this method could be expanded to actually simulate a full Turing
> > machine somehow.
>
> Undoubtedly. Recursion as a form of function application is the basis of
> lambda calculus, which is equivalent to Turing machines.
I hope so. How do you do anything complicated (e.g. simulate a Turing
machine) with lambda calculus?
> As for your method
> of doubling the ones, sure, you can generate a large number of alphabet
> characters that way. But it doesn't mean anything -- you're not writing
> your characters back into the store where they can be reused as input but
> rather out of the machine into a printer.
That's why I haven't posted any more examples -- I'm stuck. ;)
If anyone can even figure out an ISO-conforming multiplication
algorithm, I'll be thrilled beyond belief. :)
-Arthur
Ben Tels
> *Having* such a tape is the best simulation of such a tape that I can
> think of. But (you know) you can simulate a infinite tape with two
> pushdown stacks, or a single tape with only one "infinite end," or an
> infinite two-D grid, or lots of other stuff.
Yes, so what? That still doesn't have any effect on the expressive power of
the Turing machine.
>> You have a point in saying that the store of a computer is not as
>> infinite as that of a Turing machine.
>
> "As infinite"? Any real computer *is* *not* infinite.
Yes? Does that not by definition make any real computer /less/ infinite in
store size than the tape of a Turing machine?
> If my computer can calculate the factorial of ten million, but not the
> factorial of ten million million million, then that is a limit on my
> computer's "expressiveness."
No, it is not. That is the limit on the number of symbols that a computer
can contain within its store. The expressiveness of a computer and of a
Turing machine lies in the actions it can describe, independent of the size
of the store available for input and calculation. Even Alan Turing points
that out himself in his paper from 1936: the machine is ruled by its
configurations (the pair of machine state and currently scanned input
symbol), not by the size of the tape. As I recall, Turing never in fact
makes any assumptions about the length of the tape -- a tape of infinite
length is an assumption added in later treatises to avoid questions about
"what happens if you run out of tape" and so on, to make the model easier
(less cumbersome) to work with in your mind. It does not alter the
expressive power of the mechanism.
> My (real) computer is not T/C, because the
> T/C problem "Calculate ten million million million factorial." is not
> solvable by my (real) computer.
The term Turing complete does not apply to problems.
The difficulty of the statement above is this: Turing's model is of a
machine that is determined completely by its transition function and his
claims of a model of computability are based on that same function. So how
do you defend restricting Turing completeness such that a machine that can
implement that same transition function is not Turing complete, based on a
factor that does not play a role in Turing completeness?
Or think of it another way: any mechanism that can express a Turing function
is equally as expressive as a Turing machine by definition -- so if C is
not Turing complete, then neither is a Turing machine.
> The idea of the infinite tape is so that I can ask my Turing machine,
> "What is ten million factorial?" and get an answer in finite time; then
> I can ask "What is <that> factorial?" "What is <that> factorial?" ...
> and never worry about "running out" of storage. So while no *one*
> algorithm needs infinite space, there are *classes* of algorithms that
> need *unbounded* space. And a T/C computer must be able to deal with
> those.
Actually, Turing specified no rules whatsoever pertaining to the physics of
the tape -- there are no rules about wandering off the tape towards the
left, for instance. And there may be algorithms that require unbounded
space in practice, but that itself was never a consideration in the Turing
model (except to introduce an infinite tape so as not to have to dea with
it). That, however, is not a bounds on the expressiveness of a machine with
a finite tape; the rule still remains that expressiveness is determined by
the transition function. The beauty of a model is, it doesn't deal in
practical considerations (like tape lengths).
> In other words, a strictly conforming ISO C program can't use malloc()
> to get more memory when it needs it, because malloc() may return a null
> pointer. As regards the size of static objects, consider
And it may also not. That doesn't change the fact that ISO C can be used to
implement a Turing transition function.
> In other words, a strictly conforming ISO C program cannot rely on
> being able to define or access arrays of more than 65534 bytes.
So what? Arrays as a data structure have nothing to do with Turing
completeness -- there are no restrictions on memory management structures
within a Turing machine, so no such restrictions are relevant to
implementations of a machine in a programming language.
> Right. So the question remains: What is C's "expressiveness" to begin
> with?
That of a Turing machine: it has store, assignment to store, selection and
repetition. That's all you need to implement a full transition function.
> I hope so. How do you do anything complicated (e.g. simulate a Turing
> machine) with lambda calculus?
You look up the correspondence of Turing machines and lambda terms as proven
by Alan Turing and apply that to a given Turing machine to arrive at an
equivalent lambda term.
> If anyone can even figure out an ISO-conforming multiplication
> algorithm, I'll be thrilled beyond belief. :)
How about just "result = varA * varB"? That's as good an algorithm as any.
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Ben Tels wrote:
>
> Arthur J. O'Dwyer wrote:
> >> You have a point in saying that the store of a computer is not as
> >> infinite as that of a Turing machine.
> >
> > "As infinite"? Any real computer *is* *not* infinite.
>
> Yes? Does that not by definition make any real computer /less/ infinite in
> store size than the tape of a Turing machine?
Yes, but that's like calling a dead man "less alive" than a live one,
or a green light "less red" than a stop sign. "Infinite" and "finite"
in English are *not* relative terms. That's all I meant by that comment.
> > If my computer can calculate the factorial of ten million, but not the
> > factorial of ten million million million, then that is a limit on my
> > computer's "expressiveness."
>
> No, it is not. That is the limit on the number of symbols that a computer
> can contain within its store. The expressiveness of a computer and of a
> Turing machine lies in the actions it can describe, [...]
Surely "Store X into Y" is a describable action! My computer can't
do that for X = ten million million million factorial. Hence it is
less expressive (in a sense) than a computer that *can* do that.
And in the rest of that paragraph, I start to see the seed of your
misunderstanding. You seem to think that since a "Turing machine" is
equivalent to a finite state machine with an infinite store, thus it
is equivalent to an FSM with no store. (Which is wrong.)
Obviously, you can implement a finite state machine in ISO C; I've
done it many times. But there is a large class of problems which
are Turing-computable [which I occasionally abbreviate T/C], yet
cannot be computed by an FSM.
> > My (real) computer is not T/C, because the
> > T/C problem "Calculate ten million million million factorial." is not
> > solvable by my (real) computer.
>
> The term Turing complete does not apply to problems.
My abbreviation "T/C" should be understood to refer to either
"Turing-complete" or "Turing-computable," as warranted by context.
[The Church-Turing thesis states that *all* solvable computational
problems are T/C, so it's somewhat redundant, but I felt the emphasis
was important above.]
> The difficulty of the statement above is this: Turing's model is of a
> machine that is determined completely by its transition function and his
> claims of a model of computability are based on that same function.
Wrong. You are describing a finite state machine, also known as a finite
state automaton. A Turing machine is strictly more powerful than any
given FSM; consider the brace-matching problem (described in any
first-year CS course).
> Or think of it another way: any mechanism that can express a Turing function
> is equally as expressive as a Turing machine by definition -- so if C is
> not Turing complete, then neither is a Turing machine.
I don't know what a "Turing function" is -- are you referring to the state
transition function of the machine's FSM?
> > In other words, a strictly conforming ISO C program can't use malloc()
> > to get more memory when it needs it, because malloc() may return a null
> > pointer. As regards the size of static objects, consider
>
> And it may also not. That doesn't change the fact that ISO C can be used to
> implement a Turing transition function.
Again, that "Turing function." That C can implement an FSM is (almost)
obvious. But the *whole* *machine*? You've successfully demolished your
straw man, but refused to consider the question I posed.
> > In other words, a strictly conforming ISO C program cannot rely on
> > being able to define or access arrays of more than 65534 bytes.
>
> So what? Arrays as a data structure have nothing to do with Turing
> completeness -- there are no restrictions on memory management structures
> within a Turing machine, so no such restrictions are relevant to
> implementations of a machine in a programming language.
Well, you need to have *somewhere* to store data. Read the original
discussion (posted in the first contribution to this subthread), which
finishes up with two points:
A) The stack depth of ISO C is effectively infinite, and thus is a
good candidate for the construction of a Turing machine.
B) Pointer size in C is constrained, and thus you can't ever have
references to a whole bunch of objects at once (loosely speaking).
Point (B) has since been weakened by the observation that given a
suitable "mapping function," you can in fact have more than 2^16
objects "alive" at once, as long as only 2^16 distinct objects at a
time are in scope.
> > If anyone can even figure out an ISO-conforming multiplication
> > algorithm, I'll be thrilled beyond belief. :)
>
> How about just "result = varA * varB"? That's as good an algorithm as any.
Where do the values of varA and varB come from? Suppose I give you an
input stream of
(X=13 ones) (Y=2 ones)
1111111111111 11
and ask you to produce the output stream
(result=26 ones)
11111111111111111111111111
? What if X = ten million million million factorial? Does your
algorithm still produce the correct answer? (Note how my doubling
program will always produce the correct answer.)
You're getting closer...
-Arthur
Ben Tels
>> Yes? Does that not by definition make any real computer /less/ infinite
>> in store size than the tape of a Turing machine?
>
> Yes, but that's like calling a dead man "less alive" than a live one,
> or a green light "less red" than a stop sign.
In other words, undeniably correct. Trivially correct, even.
> "Infinite" and "finite"
> in English are *not* relative terms.
I beg to differ -- the whole point of cardinal numbers is that they are.
> Surely "Store X into Y" is a describable action! My computer can't
> do that for X = ten million million million factorial. Hence it is
> less expressive (in a sense) than a computer that *can* do that.
Really? As soon as I choose to represent a factorial of such a number as the
exponent of the power of ten, storing that number simply becomes writing
the number 19 into Y. You have to allow for the same freedom of
representational choice as you have in a Turing machine, after all.
> And in the rest of that paragraph, I start to see the seed of your
> misunderstanding. You seem to think that since a "Turing machine" is
> equivalent to a finite state machine with an infinite store, thus it
> is equivalent to an FSM with no store. (Which is wrong.)
Your perception of what I think is incorrect. Quite incredibly so.
>> The difficulty of the statement above is this: Turing's model is of a
>> machine that is determined completely by its transition function and his
>> claims of a model of computability are based on that same function.
>
> Wrong.
Go read his paper.
> You are describing a finite state machine, also known as a finite
> state automaton.
Oh christ. Look, basic definition: a Turing machine TM is a 7-tuple
(Q, S, G, d, q0, qa, qr)
with
Q a finite set of states
S the input alphabet and _ NOT IN S
G the tape alphabet, _ IN G and S SUBSET G
d a transition function with signature d: QxG --> QxGx{L,R}
q0 IN G the start state
qa IN G the accepting state
qr IN G the rejecting state, qr =/= qa
Within this tuple, d is called the transition function and it rules the
machine. You can verify this in any publication on computational complexity
you like (I suggest "Introduction to the Theory of Computation" by Sipser),
or you can even refer to Turing's original paper.
> I don't know what a "Turing function" is -- are you referring to the state
> transition function of the machine's FSM?
I have no idea what you're talking about. A Turing machine doesn't have a
FSM, nor has it anything to do with a FSM. A Turing function is the
transition function d that describes the behavior of the Turing machine.
> Again, that "Turing function." That C can implement an FSM is (almost)
> obvious. But the *whole* *machine*?
Again, there is no difference -- the expressive power of the Turing machine
is determined by the behavior it can demonstrated as determined by a
transition function. Any mechanism that can implement that same function is
by necessity (by definition in fact) equally as powerful as that Turing
machine.
> You've successfully demolished your
> straw man, but refused to consider the question I posed.
Unlike you, I have no need to bolster my words by hinting at failing
arguments where there are none on your part. I have not considered the
question, since it has no relevance to the topic at hand; I've already
granted you that a typical C program does not have disposal over an
infinite tape -- that does not make C anything less than Turing complete.
> Well, you need to have *somewhere* to store data.
Yes, but you are not forced into any particular representation of that data.
Nobody says that you must use data structures that are limited in size or
that you may only use one such structure or anything else that puts any
constraint on the way a datum is represented. And that is so that such
concerns will by definition have no bearing on Turing completeness and
expressive power in general.
> Read the original
> discussion (posted in the first contribution to this subthread), which
> finishes up with two points:
>
[...]
Yes, tht's all very nice, but it has nothing to do with it.
> What if X = ten million million million factorial? Does your
> algorithm still produce the correct answer? (Note how my doubling
> program will always produce the correct answer.)
There are certainly ways to squeeze a lot of ones out of a computer. It all
depends on the representation how far you get before you really run out of
space. It seems to me that you can easily represent 1 * 10^19 using 64
bits.
Programmer Dude
>>> Bonus puzzle: How many lines of code must you change to make
>>> this C code into a valid C++ translation unit? How many more must
>>> you change to make it a well-written C++ program? Well-written C?
No complaints about the versions I posted? Kewl! ;-)
> Well, here's what I'd been thinking when I wrote it down:
>
>>> #include <string.h>
>>> #include <stdlib.h>
>
> Obsolete and deprecated C++ headers.
True, but they're old friends, and they work just fine.
>>> char *old = bar;
>
> Requires a cast in C++. Accepted practice in c.l.c is to
> leave off the unnecessary cast in C.
There's more to my programming life than clc. They have a great deal
to offer, and I've learned a lot over the years, but I find some of
their views ... well ... let's just say "don't match mine" and leave
it at that.
>>> char *new = malloc(strlen(old));
>>> strcpy(old, new);
>
> As you point out, this is a bug in both C and C++.
Two, actually. I wasn't sure if they were intentional or not.
> And, of course, I was hoping you'd be inclined (as I would)
> to use std::string and new/delete in C++.
My last example did use new (you didn't use free(), so I didn't use
delete[]...for all I knew, your code frag was designed to test what
happens when you fill the heap :-).
I tend to avoid std::string and all the other STL stuff. As I said
last time, too much overhead for my taste. I do have my own String
class, though.
> That's the end of my contribution to this subthread.
Me, too.
Programmer Dude
>> You have a point in saying that the store of a computer is not as
>> infinite as that of a Turing machine.
>
> "As infinite"? Any real computer *is* *not* infinite. There's no
> degree of comparison involved.
Right. But all physical devices are finite. In any event, we're
talking about *languages*, not the platform (aren't we?).
> If my computer can calculate the factorial of ten million, but not the
> factorial of ten million million million, then that is a limit on my
> computer's "expressiveness."
Do machines have "expressiveness"? I *think* the question is, 'can you
write the algorithm' in a given language, not 'will it run on this box.'
> The idea of the infinite tape is so that I can ask my Turing machine,
> "What is ten million factorial?" and get an answer in finite time; then
> I can ask "What is <that> factorial?" "What is <that> factorial?" ...
> and never worry about "running out" of storage.
But no machine can accomplish that, so what is the real issue here?
> So while no *one* algorithm needs infinite space, there are *classes*
> of algorithms that need *unbounded* space. And a T/C computer must be
> able to deal with those.
No such machine can exist, so what is the real issue here?
>> ISO C, like most programming languages, doesn't make any assumptions
>> about store size and can address all of the store. The limited store
>> size lives in the underlying hardware, not in the language itself.
>
> Wrong! The language specified by ISO contains clauses like the following:
>
> 7.20.3.3 The malloc function
> [...]
> [#3] The malloc function returns either a null pointer or a
> pointer to the allocated space.
>
> In other words, a strictly conforming ISO C program can't use malloc()
> to get more memory when it needs it, because malloc() may return a null
> pointer.
But isn't that a hardware issue? If we assume an infinite platform with
a C implementation to match, what prevents malloc from always succeeding?
Maybe a better question for the thread is: Can C be implemented for an
infinite machine.
> -- limits of ptrdiff_t
>
> PTRDIFF_MIN -65535
> PTRDIFF_MAX +65535
>
> In other words, a strictly conforming ISO C program cannot rely on
> being able to define or access arrays of more than 65534 bytes.
The size of an individual object is limited, but is there a limit on
the total number of objects? As it is not legal to compare pointers
to different objects (only pointers with an object), it seems to me
there is no intrinsic limit.
Also, aren't the numbers above the *minimum* an implementation MUST
support? Isn't an implementation *legally* allowed to make them
*bigger*?
> So the question remains: What is C's "expressiveness" to begin
> with? Obviously, adding more capabilities (a typical malloc()
> implementation, large objects on the stack) would not make C any more
> expressive; so how expressive is ISO C right now?
I think our point is that it is as least as expressive as any other
language and, therefore, at least as T/C as any other language.
Programmer Dude
>>> Why would you use explicit casts when they are not necessary?
>>
>> Documentation. And to make C code compatible with C++ compilers.
>
> That's what's known as a circular argument: You claim that C is a
> subset of C++, because you are able to compile your C programs on a
> C++ compiler. Then you say you alter your C programs in ways that are
> not considered good style because you want them to compile on a C++
> compiler.
Good style is a matter of opinion. Consider the use of parenthesis.
Some prefer to use them rarely and allow precedence to take care of
the order of operations. Others (such as myself) use them even when
they are "not needed" to provide clarity and self-documentation.
> In fact, you have altered your C program so that it will fit with
> the type system and semantics of C++.
Nevertheless, they continue to be 100% legal C programs.
> I have never seen a C program written by an expert that systematically
> uses explicit casts between ints on the one hand and chars, unsigned
> ints, longs, etc on the other.
[shrug] False argument. I've never seen the top of Mt.Everest. Doesn't
mean is don't exist. ;-)
>> The reality of the matter is that I design code such that casts, in
>> general, are not necessary.
>
> That would be VERY hard in C. For instance you could not add 1 to a
> char....
Hard to imagine a good design that would require it (because who can
*count* on the effect of adding a number to a character).
> ...or an unsigned int or a short without either relying on implicit
> type conversion or using a cast.
Good designs don't mix types.
> You could also not use getchar() and friends to read characters.
You can if you read them into ints (which you need to do to detect
EOF, anyway)!
>> I also tend to treat warning as errors (in fact, in release builds,
>> warnings ARE errors and break the build).
>
> That's good. But the compiler should not give a warning for type
> conversions that are valid and common such as assigning a pointer
> from a void *.
I prefer that it does, because it alerts me to possible errors in
design. I don't use C much anymore, but if I did and used a C compiler,
I'd be looking for an option to turn that stuff on.
Programmer Dude
> And in the rest of that paragraph, I start to see the seed of your
> misunderstanding. You seem to think that since a "Turing machine" is
> equivalent to a finite state machine with an infinite store, thus it
> is equivalent to an FSM with no store. (Which is wrong.)
I would like to hear you describe the differences between an FSM and
a Turing Machine, because I'm not sure I follow you here. I thought
it might have something to do with a lack of a store operation in an
FSM, but you above say "finite state machine with an infinite store."
> Wrong. You are describing a finite state machine, also known as a
> finite state automaton. A Turing machine is strictly more powerful
> than any given FSM; consider the brace-matching problem (described
> in any first-year CS course).
Having used FSMs for parsing (which has included many forms of brace-
matching), I continue to be confused. I'm going to guess it has to
do with storage. By FSM, do you mean the only state contained in the
system is the position within the FSM?
> Again, that "Turing function." That C can implement an FSM is (almost)
> obvious. But the *whole* *machine*?
Save for the infinite tape, why not? Or more to the point, if C can't
do it, can *any* language?
> Well, you need to have *somewhere* to store data. Read the original
> discussion (posted in the first contribution to this subthread), which
> finishes up with two points:
>
> A) The stack depth of ISO C is effectively infinite, and thus is a
> good candidate for the construction of a Turing machine.
>
> B) Pointer size in C is constrained, and thus you can't ever have
> references to a whole bunch of objects at once (loosely speaking).
>
> Point (B) has since been weakened by the observation that given a
> suitable "mapping function," you can in fact have more than 2^16
> objects "alive" at once, as long as only 2^16 distinct objects at a
> time are in scope.
So, ... er,... it almost sounds like we all agree C is T/C? Or at least
as much so as any other language?
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Programmer Dude wrote:
>
> "Arthur J. O'Dwyer" wrote:
> >> You have a point in saying that the store of a computer is not as
> >> infinite as that of a Turing machine.
> >
> > "As infinite"? Any real computer *is* *not* infinite. There's no
> > degree of comparison involved.
>
> Right. But all physical devices are finite. In any event, we're
> talking about *languages*, not the platform (aren't we?).
Yes. ISO C, in particular.
> > If my computer can calculate the factorial of ten million, but not the
> > factorial of ten million million million, then that is a limit on my
> > computer's "expressiveness."
>
> Do machines have "expressiveness"? I *think* the question is, 'can you
> write the algorithm' in a given language, not 'will it run on this box.'
Yes, but with C the question is somewhat peculiar because of all the
restrictions placed on a strictly conforming implementation. For example,
the 'int' type may be as large as 128 bits (or larger), but it may also be
as small as 16 bits. Thus, no strictly ISO-conforming program can rely on
being able to express, e.g., ten million, as an 'int'.
> > The idea of the infinite tape is so that I can ask my Turing machine,
> > "What is ten million factorial?" and get an answer in finite time; then
> > I can ask "What is <that> factorial?" "What is <that> factorial?" ...
> > and never worry about "running out" of storage.
>
> But no machine can accomplish that, so what is the real issue here?
The C language. Forget the "machine" issue; it is a distraction.
> > So while no *one* algorithm needs infinite space, there are *classes*
> > of algorithms that need *unbounded* space. And a T/C computer must be
> > able to deal with those.
>
> No such machine can exist, so what is the real issue here?
The C language. Forget the "machine" issue; it is a distraction.
> >> ISO C, like most programming languages, doesn't make any assumptions
> >> about store size and can address all of the store. The limited store
> >> size lives in the underlying hardware, not in the language itself.
> >
> > Wrong! The language specified by ISO contains clauses like the following:
> >
> > 7.20.3.3 The malloc function
> > [...]
> > [#3] The malloc function returns either a null pointer or a
> > pointer to the allocated space.
> >
> > In other words, a strictly conforming ISO C program can't use malloc()
> > to get more memory when it needs it, because malloc() may return a null
> > pointer.
>
> But isn't that a hardware issue? If we assume an infinite platform with
> a C implementation to match, what prevents malloc from always succeeding?
Nothing. But nothing prevents it from *failing*, either; and if your
program fails when malloc fails, then it obviously does not solve the
problem.
> Maybe a better question for the thread is: Can C be implemented for an
> infinite machine.
No, no, no! Forget the "machine"! That is a distraction! Concentrate
on the question: Can a Turing machine be perfectly simulated in ISO
standard C, using no implementation-defined behavior except that forced
upon us by the functions getchar() and putchar()?
> > -- limits of ptrdiff_t
> >
> > PTRDIFF_MIN -65535
> > PTRDIFF_MAX +65535
> >
> > In other words, a strictly conforming ISO C program cannot rely on
> > being able to define or access arrays of more than 65534 bytes.
>
> The size of an individual object is limited, but is there a limit on
> the total number of objects? As it is not legal to compare pointers
> to different objects (only pointers with an object), it seems to me
> there is no intrinsic limit.
Pointers to different objects may be compared for equality. This
was covered in the previous thread; consider the program
int main(void)
{
int i0, *pi0 = &i0;
int i1, *pi1 = &i1;
int i2, *pi2 = &i2;
[...]
int i65536, *pi65536 = &i65536;
int *n = 0;
assert(CHAR_BIT == 8);
assert(sizeof(int*) == 2);
if (pi0 == pi1) printf("THIS PROGRAM CONTAINS UNDEFINED BEHAVIOR\n");
if (pi0 == pi2) printf("THIS PROGRAM CONTAINS UNDEFINED BEHAVIOR\n");
if (pi0 == pi3) printf("THIS PROGRAM CONTAINS UNDEFINED BEHAVIOR\n");
[...]
if (pi65535 == pi65536) printf("THIS PROGRAM CONTAINS UNDEFINED"
" BEHAVIOR\n");
if (pi65536 == n) printf("THIS PROGRAM CONTAINS UNDEFINED BEHAVIOR\n");
return 0;
}
Since there can be only 65536 different 16-bit pointer representations,
and in this simple program we have tried to create 65537 different and
distinct pointer values (pi0, pi1, ... pi65536, n), this program must
exhibit undefined behavior.
Now consider
void foo(long int L)
{
int i, *pi = &i;
if (L == 0L) return;
foo(L-1);
}
int main(void) { foo(65536L); return 0; }
In this simple program, we create 65537 different and distinct int objects
on the "stack," and point 65537 distinct pointers at those objects. But
here there is no undefined behavior, because the Standard implicitly
allows the mapping function from pointer representations to pointer values
to change at any time.
> Also, aren't the numbers above the *minimum* an implementation MUST
> support? Isn't an implementation *legally* allowed to make them
> *bigger*?
Of course. But no implementation is ever required to do so.
> > So the question remains: What is C's "expressiveness" to begin
> > with? Obviously, adding more capabilities (a typical malloc()
> > implementation, large objects on the stack) would not make C any more
> > expressive; so how expressive is ISO C right now?
>
> I think our point is that it is as least as expressive as any other
> language and, therefore, at least as T/C as any other language.
I think I have read that Standard Lisp is provably T/C.
I have never read of a similar proof for Standard C, and I find
the question quite intriguing. YMMV.
-Arthur
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Ben Tels wrote:
>
I am once again exercising my threadly prerogative to devote this
subthread to the mathematical side of the argument. The actual
C-related discussion can take place in the other half of this
thread, which I intend to start on right after this response.
> Arthur J. O'Dwyer wrote:
> > Surely "Store X into Y" is a describable action! My computer can't
> > do that for X = ten million million million factorial. Hence it is
> > less expressive (in a sense) than a computer that *can* do that.
>
> Really? As soon as I choose to represent a factorial of such a number as the
> exponent of the power of ten, storing that number simply becomes writing
> the number 19 into Y. You have to allow for the same freedom of
> representational choice as you have in a Turing machine, after all.
In which case the task becomes: "Convert a 32-bit twos-complement
binary integer, X, into a string of consecutive '1's of length
(10**X) factorial." My computer can't do *that*, either.
> > You are describing a finite state machine, also known as a finite
> > state automaton.
>
> Oh christ. Look, basic definition: a Turing machine TM is a 7-tuple
>
> (Q, S, G, d, q0, qa, qr)
>
> with
>
> Q a finite set of states
> S the input alphabet and _ NOT IN S
(What is S used for?)
> G the tape alphabet, _ IN G and S SUBSET G
> d a transition function with signature d: QxG --> QxGx{L,R}
> q0 IN G the start state
> qa IN G the accepting state
> qr IN G the rejecting state, qr =/= qa
Or, equivalently, a Turing machine can be described by an ordered pair
(F, d)
with
F a finite state machine described by (Q, X: QxG->Q, q0, qa, qr)
where X is the FSM's transition function
and G, the tape alphabet, is defined to be {0,1}
d an "action table" with signature d: Q -> Gx{L,R}
> I have no idea what you're talking about. A Turing machine doesn't have a
> FSM, nor has it anything to do with a FSM.
Tee hee!
But I'm glad you cleared that up, anyway.
> > Again, that "Turing function." That C can implement an FSM is (almost)
> > obvious. But the *whole* *machine*?
>
> Again, there is no difference -- the expressive power of the Turing machine
> is determined by the behavior it can demonstrated as determined by a
> transition function. Any mechanism that can implement that same function is
> by necessity (by definition in fact) equally as powerful as that Turing
> machine.
Bzzt!
English text can *describe* a Turing machine. English text cannot
*implement* a Turing machine. Do you see the difference yet?
> > You've successfully demolished your
> > straw man, but refused to consider the question I posed.
>
> Unlike you, I have no need to bolster my words by hinting at failing
> arguments where there are none on your part.
Why, thank you!
> There are certainly ways to squeeze a lot of ones out of a computer. It all
> depends on the representation how far you get before you really run out of
> space. It seems to me that you can easily represent 1 * 10^19 using 64
> bits.
Ten million million million factorial is approximately
1e19 * 1e18**9e18 * 1e17**9e17 * 1e18**9e16 * ... * 1**10
> 1e18**9e18 == 1e(18*9e18) == 1e(162e18)
> 1e(1e20)
20
10
== 10
64
That's more than 2 by a lot.
-Arthur
Arthur J. O'Dwyer
This half of the subthread, I devote to serious C and/or
programming talk. No theory discussions, please. Just
implementations.
On Mon, 28 Apr 2003, Ben Tels wrote:
>
> A Turing function is the
> transition function d that describes the behavior of the Turing machine.
This is almost trivial to write in C (I think). The trick is getting
the C language to simulate the effect of calling that function repeatedly
as if it were really attached to an infinite tape of the sort Turing
(or his followers) imagined.
> > Again, that "Turing function." That C can implement an FSM is (almost)
> > obvious. But the *whole* *machine*?
In other words, if I give you (the gentle reader) a well-defined and T/C
math problem to solve, can you write a program in strict ISO C which will
solve the problem?
Examples:
Given a number in unary notation, double that number. (Solved.)
Given a positive number in binary notation ('0' and '1', MSB first,
terminated by any character not a '0' or a '1'), print out that
number in unary notation.
Given two unary numbers separated by a '0', add them and print
the result in unary notation. (Solved.)
Given two unary numbers separated by a '0', multiply them and
print the result in unary notation.
Given a number in binary notation, print '0' if it is prime and
'1' if it is not prime.
> I have not considered the question, since it has no relevance to the
> topic at hand; I've already granted you that a typical C program does
> not have disposal over an infinite tape -- that does not make C
> anything less than Turing complete.
Well, if it can't access an arbitrarily large store, then it provably
can't solve a very large class of T/C (Turing-computable) problems.
The question you refuse to consider is:
Can one simulate an arbitrarily large store in ISO-conforming C,
given all the restrictions set down by the letter of the Standard?
Recap of technical points:
malloc() is useless in a strictly conforming program.
CHAR_BIT is not required to be any larger than 8.
sizeof(long) is not required to be any larger than ceil(32./CHAR_BIT).
Undefined behavior is Not Allowed by fiat.
The only implementation-defined behavior I can think of to allow
is the use of getchar() to read input, and putchar() to write
output, of characters in the execution character set; also by fiat.
The relationship between pointer values and their representations
is somewhat tricky.
Recursion is potentially useful -- this is the question which
has actual ramifications in computer science in general.
As an annoying gesture, I hereby offer to send a check for $5.13 (more
than twice the offer of Knuth!) to the first person to submit a working
ISO C program that multiplies two arbitrarily large space-separated,
base-two positive numbers in the following fashion:
Input-> 1001 10\n
Output-> 10010\n
Input-> 1 10111\n
Output-> 10111\n
Input-> 10110 10100\n
Output-> 110111000\n
Seriously, I'll send you a check. Because I want to know
whether it's even possible or not.
-Arthur
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Programmer Dude wrote:
>
> "Arthur J. O'Dwyer" wrote:
> > And in the rest of that paragraph, I start to see the seed of your
> > misunderstanding. You seem to think that since a "Turing machine" is
> > equivalent to a finite state machine with an infinite store, thus it
> > is equivalent to an FSM with no store. (Which is wrong.)
>
> I would like to hear you describe the differences between an FSM and
> a Turing Machine, because I'm not sure I follow you here. I thought
> it might have something to do with a lack of a store operation in an
> FSM, but you above say "finite state machine with an infinite store."
Part of the fundamentals of CS is the idea of "models of computation."
A finite state machine, or FSM, is one of the simplest models, consisting
only of an alphabet; a set of states, of which one is the start state, a
few are "accepting" states, and the rest are "rejecting" states; and a
"transition function" F:QxG->Q that says how to go from one state to the
other. In C, one might write:
void IsItEven(void)
{
enum States { IS_EVEN, IS_ODD, START_STATE = IS_EVEN };
int current_state = START_STATE;
int next_symbol;
while ((next_symbol = getchar()) != EOF) {
/* This is the transition function. */
switch (current_state)
{
case IS_EVEN:
switch (next_symbol) {
case '0': current_state = IS_EVEN; break;
case '1': current_state = IS_ODD; break;
default: goto END;
}
break;
case IS_ODD:
switch (next_symbol) {
case '0': current_state = IS_EVEN; break;
case '1': current_state = IS_ODD; break;
default: goto END;
}
break;
}
}
END:
if (current_state == IS_EVEN) accept();
if (current_state == IS_ODD) reject();
}
Most usually, you'll see an FSM depicted as a bunch of "bubbles" (states)
connected by labeled lines (the transitions coded for by the transition
function). Here is an excellent explanation in the form of lecture
slides, which I recommend to Ben Tels also:
http://www.discretemath.com/Materials/Lectures/Lecture14/slide/slide1.html
More powerful than an FSM is an FSM with one stack (a brace-matcher); more
powerful than *that* is an FSM with *two* stacks (a Turing machine).
The stacks are where the machine stores its arbitrarily large state
information, BTW. If you have no stack, then you have no infinite store,
and it's hard for you to do much of interest.
> > Wrong. You are describing a finite state machine, also known as a
> > finite state automaton. A Turing machine is strictly more powerful
> > than any given FSM; consider the brace-matching problem (described
> > in any first-year CS course).
>
> Having used FSMs for parsing (which has included many forms of brace-
> matching), I continue to be confused. I'm going to guess it has to
> do with storage. By FSM, do you mean the only state contained in the
> system is the position within the FSM?
Of course. An FSM by definition doesn't contain *anything* that isn't
contained within itself.
And brace-matching (e.g., finding out whether a given expression is
a valid C expression) is obviously T/C but not FSM/C. This is also
explained very nicely in the lecture slideshow.
> > Again, that "Turing function." That C can implement an FSM is (almost)
> > obvious. But the *whole* *machine*?
>
> Save for the infinite tape, why not? Or more to the point, if C can't
> do it, can *any* language?
Save for the infinite tape, no reason. Save for their lack of wings,
no reason pigs don't fly.
As I said somewhere else, I think Lisp is T/C. And a language that's
easy to prove T/C is the following:
A C-like language in which all numbers are bignums that (magically)
expand to fit their contents.
> So, ... er,... it almost sounds like we all agree C is T/C? Or at least
> as much so as any other language?
It does *almost* sound like it, yeah. The problem with trying to have
this sort of discussion, which Daniel Vallstrom ran into last time on
c.l.c, was that by the time the linguistic differences had been ironed
out, everyone had lost interest in the actual puzzle. I hope that
won't happen here.
-Arthur
Programmer Dude
> Can one simulate an arbitrarily large store in ISO-conforming C,
> given all the restrictions set down by the letter of the Standard?
Are the standard libraries part of the standard? If so, can one use
file I/O to simulate the tape? Can we in this way fob off the space
and pointer issues to "infinite disk space"?
Programmer Dude
> ...with C the question is somewhat peculiar because of all the
> restrictions placed on a strictly conforming implementation. [...]
> Thus, no strictly ISO-conforming program can rely on being able to
> express, e.g., ten million, as an 'int'.
I'm not at all convinced native data types should be a limit. I'm also
not convinced the minimal subset of pure ISO C should be a limit. To
put it elsewise, if ISO C *allows* extensions that are helpful, why not
use them?
>>> 7.20.3.3 The malloc function
>>> [...]
>>
>> But isn't that a hardware issue? If we assume an infinite platform with
>> a C implementation to match, what prevents malloc from always succeeding?
>
> Nothing. But nothing prevents it from *failing*, either; and if your
> program fails when malloc fails, then it obviously does not solve the
> problem.
If your Turing Tape breaks or jams,..... isn't that the same thing?
If you can postulate a machine with an infinite, always working tape,
why not a malloc that never fails?
> Can a Turing machine be perfectly simulated in ISO standard C, using
> no implementation-defined behavior except that forced upon us by the
> functions getchar() and putchar()?
I vote yes. If I'm forgetting about machine limits, then these functions
always work as expected (for they would only fail for machine reasons).
>> The size of an individual object is limited, but is there a limit on
>> the total number of objects? As it is not legal to compare pointers
>> to different objects (only pointers with an object), it seems to me
>> there is no intrinsic limit.
>
> Pointers to different objects may be compared for equality.
(Why do I have a nagging sense you can only compare them to NULL or to
another pointer to the same object?)
Nevertheless, this is a restricted operation (you may ONLY compare them
for equality, not a relationship). Hence, an implementation that handles
ultra-mega-super-pointers need only be able to recognize if two of these
magic pointer objects are equal.
>> Also, aren't the numbers above the *minimum* an implementation MUST
>> support? Isn't an implementation *legally* allowed to make them
>> *bigger*?
>
> Of course. But no implementation is ever required to do so.
Right, but our Turing Implementation does! ;-)
>> I think our point is that it is as least as expressive as any other
>> language and, therefore, at least as T/C as any other language.
>
> I think I have read that Standard Lisp is provably T/C.
> I have never read of a similar proof for Standard C, and I find
> the question quite intriguing. YMMV.
It'd be interesting to see that proof and what it involves (and, in
particular, why it doesn't apply to other languages).
Programmer Dude
>> I would like to hear you describe the differences between an FSM and
>> a Turing Machine, because I'm not sure I follow you here.
>
> Part of the fundamentals of CS is the idea of "models of computation."
> A finite state machine, or FSM, is one of the simplest models,..
Ah, okay, I understand. I happen to love FSMs and tend to use them any
time I need to parse serial input. I got confused between 'implementation
of an FSM (which includes using memory)' and 'theoretical FSM'.
I'm with ya now! ;-)
> Most usually, you'll see an FSM depicted as a bunch of "bubbles" (states)
> connected by labeled lines (the transitions coded for by the transition
> function).
I've also seen a model where the functionality is in both where the "arrow"
leaves one bubble and where it enters another. This allows an interesting
state of affairs in combining bits of functionality. I haven't quite come
up with a good use for this, however.
(Again, I'm speaking more towards a practical implementation model then the
theoretical CS model.)
> More powerful than an FSM is an FSM with one stack (a brace-matcher); more
> powerful than *that* is an FSM with *two* stacks (a Turing machine).
And since, in my world, an FSM is always an implemented thing, it always
comes with the necessary storage. Hence my confusion.
>> Save for the infinite tape, why not? Or more to the point, if C can't
>> do it, can *any* language?
>
> Save for the infinite tape, no reason.
And since no *implementation* can have an infinite anything, no language
*implementation* can be truly T/C. Yes?
As I understand it the question narrows down to whether a strict ISO C
can implement a Turing machine. Seems to me, if we allow I/O, then it
can.
> As I said somewhere else, I think Lisp is T/C. And a language that's
> easy to prove T/C is the following:
>
> A C-like language in which all numbers are bignums that (magically)
> expand to fit their contents.
Such as Smalltalk (or Lisp)? Again, it seems you could implement this
in C, although it's clearly not native to the language.
But here's the thing. A C string is a list of non-zero chars terminated
by a zero. Given I/O, how can that not be a Turing Tape?
> It does *almost* sound like it, yeah. The problem with trying to have
> this sort of discussion, which Daniel Vallstrom ran into last time on
> c.l.c, was that by the time the linguistic differences had been ironed
> out, everyone had lost interest in the actual puzzle. I hope that
> won't happen here.
Okay, I'll try to hang in there. I like your little puzzles and maybe
will try to find the time to attempt an implementation. But I have to
admit, I don't find the theoretical question very interesting. It sorta
seems like the answer (as always in CS) is: It Depends.
Ben Tels
> I would like to hear you describe the differences between an FSM and
> a Turing Machine, because I'm not sure I follow you here. I thought
> it might have something to do with a lack of a store operation in an
> FSM, but you above say "finite state machine with an infinite store."
Good point -- that IS nonsense. A finite state machine doesn't have a store
of any kind. He's thinking of a pushdown automaton, which has a stack.
A finite state machine is a machine with a finite number of states. It
consumes a token from some input source and based on that token makes a
transition from one state to the next until it gets stuck in an accepting
state or in a non-accepting state where the next input (if there is any)
does not facilitate a state transition. A FSM can accept and recognize
languages with words whose recognition requires no context or "stepping
back" through the input.
A pushdown automaton is a device with a set of states and a stack. It
accepts an input, pushes symbols onto the stack and transitions to a new
state based on that input. Or it pops symbols from the stack. But it cannot
look backwards through the stack and it usually does not remember exactly
what the input was -- it can only create a certain stack top and state
combination that allows it to continue onwards. Of course popping symbols
from the stack allows you to return to a previous point of knowledge and
proceed from there, but you no longer have the exact, corresponding input
available.
And a Turing machine lets you have it all. Moving forward and back at will
through the input, changing it at will, whatever.
> Having used FSMs for parsing (which has included many forms of brace-
> matching), I continue to be confused.
Correction -- you've used a PDA for parsing. Very few languages can be
parsed by a FSM. But you undoubtedly have used a FSM as a lexical analyzer.
> I'm going to guess it has to
> do with storage. By FSM, do you mean the only state contained in the
> system is the position within the FSM?
Nah -- he means PDA, not FSM.
> Save for the infinite tape, why not? Or more to the point, if C can't
> do it, can *any* language?
Not unless it has an actual Turing machine to run its programs. He is
contending that programming languages cannot be Turing complete owing to
the practical constraints of underlying hardware.
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Programmer Dude wrote:
>
> "Arthur J. O'Dwyer" wrote:
> > Can one simulate an arbitrarily large store in ISO-conforming C,
> > given all the restrictions set down by the letter of the Standard?
>
> Are the standard libraries part of the standard? If so, can one use
> file I/O to simulate the tape? Can we in this way fob off the space
> and pointer issues to "infinite disk space"?
The standard libraries are indeed part of the Standard. (You can see
a draft version of the latest C standard online; Google for "N869".)
Here's the dirt on the file operations:
[#8] Functions that open additional (nontemporary) files
require a file name, which is a string. The rules for
composing valid file names are implementation-defined.
Whether the same file can be simultaneously open multiple
times is also implementation-defined.
In other words, you can't say FILE *p = fopen("c:\\data.dat","w");
and expect it to do The Right Thing (especially if you're using
Unix ;) .
However, you can open up to TMP_MAX >= 25 temporary files, as
per section 7.19.4.4.6 of N869. These files can be accessed using
fopen(), followed by the usual stream I/O functions. I don't
know what the committee intended by the language there, but I
don't see any constraints on the number of bytes you can write
to a file. Except for the constraint that a write error may
occur at any time(!).
So your point is well-taken; I must be more specific in the
"un-constraints" I am going to impose on the puzzle.
An "acceptable" program must be well-defined (exhibit no undefined
behavior on any legitimate input whatsoever) and strictly conforming
to the standard, as per section 4.5:
[#5] A strictly conforming program shall use only those
features of the language and library specified in this
International Standard.2) It shall not produce output
dependent on any unspecified, undefined, or implementation-
defined behavior, and shall not exceed any minimum
implementation limit.
except for the following "un-constraints":
It is guaranteed that the getchar() function shall never give
a read error.
It is guaranteed that the putchar() function shall never give
a write error when used to write a character in the execution
character set.
Okay, I think that expresses my peculiar ideas well enough. The idea
is to re-iterate that regular file I/O is not guaranteed to work, while
still allowing stdin and stdout to work "normally."
-Arthur
Arthur J. O'Dwyer
On Mon, 28 Apr 2003, Programmer Dude wrote:
>
> > ...with C the question is somewhat peculiar because of all the
> > restrictions placed on a strictly conforming implementation. [...]
> > Thus, no strictly ISO-conforming program can rely on being able to
> > express, e.g., ten million, as an 'int'.
>
> I'm not at all convinced native data types should be a limit. I'm also
> not convinced the minimal subset of pure ISO C should be a limit.
I'm *making* ISO C a "limit," because if I allow the use of, e.g.,
English text, in place of standard C, the problem becomes trivial.
And where do you draw the line between "non-standard C" and "English"?
> To put it elsewise, if ISO C *allows* extensions that are helpful,
> why not use them?
Because it *allows* the *lack* of extensions, also. To put it another
way, do you understand why the following program is silly?
/* print "hello world" in Russian */
int main()
{
printf("%s", (char *) 100129812943);
}
Now, that is a perfectly legal program on *some* implementation of C,
that does in fact print "hello world" in Russian when the program is
executed. But it's still not a strictly conforming C program, because
it relies on implementation-defined (and undefined) behavior. (See my
last post in response to your other reply, for the only two
"un-constraints" I'm willing to put on the puzzle.)
> >>> 7.20.3.3 The malloc function
> >>> [...]
> >>
> >> But isn't that a hardware issue? If we assume an infinite platform with
> >> a C implementation to match, what prevents malloc from always succeeding?
> >
> > Nothing. But nothing prevents it from *failing*, either; and if your
> > program fails when malloc fails, then it obviously does not solve the
> > problem.
>
> If your Turing Tape breaks or jams,..... isn't that the same thing?
> If you can postulate a machine with an infinite, always working tape,
> why not a malloc that never fails?
I can indeed *postulate* a no-fail malloc. But the ISO committee that
designed the C standard did *not* postulate such a malloc.
Also, that would make the question trivial, and thus not worth asking.
[snipped]
> > Pointers to different objects may be compared for equality.
>
> (Why do I have a nagging sense you can only compare them to NULL or to
> another pointer to the same object?)
I certainly can't tell you.
> Nevertheless, this is a restricted operation (you may ONLY compare them
> for equality, not a relationship). Hence, an implementation that handles
> ultra-mega-super-pointers need only be able to recognize if two of these
> magic pointer objects are equal.
... Go on, I'm listening.
> > I think I have read that Standard Lisp is provably T/C.
> > I have never read of a similar proof for Standard C, and I find
> > the question quite intriguing. YMMV.
>
> It'd be interesting to see that proof and what it involves (and, in
> particular, why it doesn't apply to other languages).
Googling for (lisp "turing completeness") hits on a "Mechanical Proof
of the Turing Completeness of Pure Lisp," but I don't know enough
about functional programming to follow the paper.
As to why it doesn't apply to other languages, I can tell you right
now that Turbo Pascal v3.0 is *not* T/C, because it is tied so tightly
to the 64K-segment architecture of the IBM PC. In fact, *any* actual
implementation of any language is going to be non-T/C, because of
the finiteness of the universe and all that. The cool thing about
C (and I presume Standard Lisp also) is that it is *not* tied to any
implementation, so we can reason about it in the abstract.
HTH,
-Arthur
Jim Rogers
Hey Chris, it sure sounds like you want to program C as though
it was Ada. ;-)
Jim Rogers
Ben Tels
> In which case the task becomes: "Convert a 32-bit twos-complement
> binary integer, X, into a string of consecutive '1's of length
> (10**X) factorial." My computer can't do *that*, either.
As a result of the physical size limitations of your computer's memory
(depending on what you mean by converting something into a string of ones).
However, your computer is certainly capable of implementing and executing
the algorithm that solves the problem if we ignore the physical size
constraints. It is in that ability that expressiveness is measured.
>> S the input alphabet and _ NOT IN S
> (What is S used for?)
It is the alphabet of which the input may consist.
> Or, equivalently, a Turing machine can be described by an ordered pair
>
> (F, d)
> with
> F a finite state machine described by (Q, X: QxG->Q, q0, qa, qr)
> where X is the FSM's transition function
> and G, the tape alphabet, is defined to be {0,1}
> d an "action table" with signature d: Q -> Gx{L,R}
In this definition, you have made it impossible for the symbol on the tape
to be of influence over the symbol with which it is replaced or which
direction the head is moved. So I doubt very seriously that it is
equivalent. For instance (although it is late right now) I do not see how
you are going to come up with an equivalent set of actions in your
defintion for a TM that exhibits this behavior:
(Q0, 0) --> (Q1, 1, R)
from this configuration
_____\ /____________
|0|X|Y| (Q0)
--------------------
where X and Y are either 0 or 1 if the transition function also includes
(Q1, 1, L).
You cannot do it by associating Q1 with (1, R) in your action table, since
the association must be with (1,L). So to place the head on the position
with X in state Q1, you must approach that position from the left. Which I
suppose is doable if Y happens to be 0, but if it is not I do believe you
to be screwed since you cannot arrive at the position of X in Q1 from the
right without replacing Y=0 with a 1.
>> I have no idea what you're talking about. A Turing machine doesn't have a
>> FSM, nor has it anything to do with a FSM.
>
> Tee hee!
What are you "tee hee"ing about? The definition you gave above is not
equivalent. Not to mention that you are completely abusing the term finite
state machine to cover PDA's as well.
> English text can *describe* a Turing machine. English text cannot
> *implement* a Turing machine. Do you see the difference yet?
So what? All you've shown is that English is not Turing complete. What does
that have to do with anything?
>> Unlike you, I have no need to bolster my words by hinting at failing
>> arguments where there are none on your part.
>
> Why, thank you!
That was not a compliment and most certainly not an assertion that you have
made no errors (for the lord knows you have). It was, however, a remark to
the effect that you need not attempt to weaken my argument by hinting at
errors that I have supposedly made without actually producing any errors;
it is a rhetorical tactic to which I am immune.
> 64
> That's more than 2 by a lot.
Which still doesn't affect expressive power in the sense of Turing
completeness. If you insist on storing all those ones in individual memory
cells, all it means is that you will have to buy more memory.
Ben Tels
> This half of the subthread, I devote to serious C and/or
> programming talk. No theory discussions, please. Just
> implementations.
This is nonsense. You're trying to sneak in a factor that has nothing to do
with Turing completeness.
Programmer Dude
>>> Can one simulate an arbitrarily large store in ISO-conforming C,
>>> given all the restrictions set down by the letter of the Standard?
>>
>> Are the standard libraries part of the standard? If so, can one use
>> file I/O to simulate the tape? Can we in this way fob off the space
>> and pointer issues to "infinite disk space"?
>
> The standard libraries are indeed part of the Standard. (You can see
> a draft version of the latest C standard online; Google for "N869".)
I've had it for a long time. I just wanted to check, since you're
setting the rules. One *could* say only the language itself is proper
meat for this discussion (which would pretty much provide a clear
answer, wouldn't it!).
> [#8] Functions that open additional (nontemporary) files
> require a file name, which is a string. The rules for
> composing valid file names are implementation-defined.
> Whether the same file can be simultaneously open multiple
> times is also implementation-defined.
>
> In other words, you can't say FILE *p = fopen("c:\\data.dat","w");
> and expect it to do The Right Thing (especially if you're using
> Unix ;) .
Or VMS. Is this why you're sticking to stdin and stdout?
> So your point is well-taken; I must be more specific in the
> "un-constraints" I am going to impose on the puzzle.
>
> An "acceptable" program must be well-defined (exhibit no undefined
> behavior on any legitimate input whatsoever) and strictly conforming
> to the standard, as per section 4.5:
Hmmm. Does this allow or prevent:
FILE* fin = fopen("ttin", "r");
FILE* fout = fopen("ttout", "w");
> except for the following "un-constraints":
>
> It is guaranteed that the getchar() function shall never give
> a read error.
>
> It is guaranteed that the putchar() function shall never give
> a write error when used to write a character in the execution
> character set.
>
> Okay, I think that expresses my peculiar ideas well enough. The idea
> is to re-iterate that regular file I/O is not guaranteed to work, while
> still allowing stdin and stdout to work "normally."
I'm not sure I can see a way to generate a T/M with only stdin and stdout.
**********************
I'm going to compress things a bit and answer your next reply here:
"Arthur J. O'Dwyer" wrote:
>> I'm not at all convinced native data types should be a limit. I'm also
>> not convinced the minimal subset of pure ISO C should be a limit.
>
> I'm *making* ISO C a "limit," because if I allow the use of, e.g.,
> English text, in place of standard C, the problem becomes trivial.
> And where do you draw the line between "non-standard C" and "English"?
Well, I didn't mean go from minimal ISO C to English. I just meant
allow a reasonably extended (as allowed by the spec) implementation.
>> To put it elsewise, if ISO C *allows* extensions that are helpful,
>> why not use them?
>
> Because it *allows* the *lack* of extensions, also.
So, in a sense you want a Turing Machine in ISO C that is 100% portable
and guarenteed to work on any implementation?
> To put it another way, do you understand why the following program
> is silly?
Yes.
>> If your Turing Tape breaks or jams,..... isn't that the same thing?
>> If you can postulate a machine with an infinite, always working tape,
>> why not a malloc that never fails?
>
> I can indeed *postulate* a no-fail malloc. But the ISO committee that
> designed the C standard did *not* postulate such a malloc.
>
> Also, that would make the question trivial, and thus not worth asking.
Considering that a "pure C" implementation (no libraries) would obviously
not be T/C, and that an extended one is... the truth lies somewhere
between. Given your constraints, I'm thinking... no.
>> It'd be interesting to see that proof and what it involves (and, in
>> particular, why it doesn't apply to other languages).
>
> Googling for (lisp "turing completeness") hits on a "Mechanical Proof
> of the Turing Completeness of Pure Lisp," but I don't know enough
> about functional programming to follow the paper.
End of day for me. I'll check it out tomorrow.
Programmer Dude
> Hey Chris, it sure sounds like you want to program C as though
> it was Ada. ;-)
ROFL!!!
Long as I get my curly braces and "line noise" syntax! ;-)
Arthur J. O'Dwyer
On Tue, 29 Apr 2003, Ben Tels wrote:
>
> Arthur J. O'Dwyer wrote:
>
> > In which case the task becomes: "Convert a 32-bit twos-complement
> > binary integer, X, into a string of consecutive '1's of length
> > (10**X) factorial." My computer can't do *that*, either.
[Ben suggests to ignore space constraints.]
But that's my whole point! *My* computer *is* space-constrained!
> > Or, equivalently, a Turing machine can be described by an ordered pair
> >
> > (F, d)
> > with
> > F a finite state machine described by (Q, X: QxG->Q, q0, qa, qr)
> > where X is the FSM's transition function
> > and G, the tape alphabet, is defined to be {0,1}
> > d an "action table" with signature d: Q -> Gx{L,R}
>
> In this definition, you have made it impossible for the symbol on the tape
> to be of influence over the symbol with which it is replaced or which
> direction the head is moved. So I doubt very seriously that it is
> equivalent. For instance (although it is late right now) I do not see how
> you are going to come up with an equivalent set of actions in your
> [definition] for a TM that exhibits this behavior:
>
> (Q0, 0) --> (Q1, 1, R)
>
> from this configuration
>
> _____\ /____________
> |0|X|Y| (Q0)
> --------------------
>
> where X and Y are either 0 or 1 if the transition function also includes
>
> (Q1, 1, L).
Let me see if I understand the procedure behind this machine.
It begins in Q0. If the symbol on the tape is 0, it changes it
to a 1, moves right, and goes to state Q1.
From state Q1, it ... does it change the tape to a 1 and move left
unconditionally? Is that what a lone (Q1, 1, L) indicates?
In any case, to change a 0 to a 1 on the tape, while moving the head one
space to the right, I could write my machine as follows.
F:
(R0, 0) -> R1
(R1, 0) -> R20
(R1, 1) -> R21
(R20, 0) -> R30
(R20, 1) -> R31
(R21, 0) -> R32
(R21, 1) -> R33
q0 = R0
qa = { R30, R31, R32, R33 } (Translating the set of states to a single
acceptance state is left as an exercise.)
d:
R1 -> (1, L)
R20 -> (0, R)
R21 -> (1, R)
R30, R32 -> (0, R)
R31, R33 -> (1, R)
>
> You cannot do it by associating Q1 with (1, R) in your action table, since
> the association must be with (1,L).
The trick is to use more than 2 states. In the above example, I used
eight different states, although I think three or four would have
sufficed. (The idea is that first q:=F(q,g) is executed, and then
the tape is updated as per d(q), by the way.)
-Arthur
Ben Tels
> Let me see if I understand the procedure behind this machine.
> It begins in Q0. If the symbol on the tape is 0, it changes it
> to a 1, moves right, and goes to state Q1.
> From state Q1, it ... does it change the tape to a 1 and move left
> unconditionally? Is that what a lone (Q1, 1, L) indicates?
Someday I'm going to learn not to post in the middle of the night. The
general idea is to convey that the stated machines are not equivalent
because new state alone in general is not sufficient to determine machine
actions. Although on consideration, you might be creating an equivalent
machine at the cost of exploding the number of states upwards -- I'll have
to think about it more when I have less cotton in my head.
Robert STRANDH
> Good style is a matter of opinion.
Not as much as people think. A large part of good style is to follow
the conventions developed over the years by the members (especially
the experts) of the community. Good style is not just for pleasure.
Just like in natural languages, good style serves a communication
purpose. It makes communication faster and less ambiguous. If good
style were a matter of personal opinion, such advantages would largely
disappear.
> > In fact, you have altered your C program so that it will fit with
> > the type system and semantics of C++.
>
> Nevertheless, they continue to be 100% legal C programs.
Sure, but they are no longer idiomatic. The set of idiomatic programs
is much smaller than the set of legal programs. Good style is mainly
about respecting programming idioms of the community.
> > I have never seen a C program written by an expert that systematically
> > uses explicit casts between ints on the one hand and chars, unsigned
> > ints, longs, etc on the other.
>
> [shrug] False argument. I've never seen the top of Mt.Everest. Doesn't
> mean is don't exist. ;-)
Perhaps if I add "and I have looked at many C programs written by
experts over the years", the argument would satisfy you?
> >> The reality of the matter is that I design code such that casts, in
> >> general, are not necessary.
> >
> > That would be VERY hard in C. For instance you could not add 1 to a
> > char....
>
> Hard to imagine a good design that would require it (because who can
> *count* on the effect of adding a number to a character).
Chars in C are not characters, just small integers.
> > ...or an unsigned int or a short without either relying on implicit
> > type conversion or using a cast.
>
> Good designs don't mix types.
So you are saying that this is bad style :
unsigned int counter;
...
counter += 2;
Could you please tell me what you would do in this situation, i.e. how
would you add 2 to this counter represented as an unsigned int.
> > You could also not use getchar() and friends to read characters.
>
> You can if you read them into ints (which you need to do to detect
> EOF, anyway)!
But then you probably want to put the non-EOF result in a character
string. If I understand you right, you can't do that without having a
badly designed C program, since it would mix different types.
> > conversions that are valid and common such as assigning a pointer
> > from a void *.
>
> I prefer that it does, because it alerts me to possible errors in
> design. I don't use C much anymore, but if I did and used a C compiler,
> I'd be looking for an option to turn that stuff on.
I see it exactly the opposite way. By forcing the programmer to put
in casts in these situations in order to avoid warnings, some subtle
hidden errors may persist. In addition, the compiler would force me
to use non-idiomatic C, which is even worse.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
Ben Tels
> Arthur J. O'Dwyer wrote:
>
>> Let me see if I understand the procedure behind this machine.
>> It begins in Q0. If the symbol on the tape is 0, it changes it
>> to a 1, moves right, and goes to state Q1.
>> From state Q1, it ... does it change the tape to a 1 and move left
>> unconditionally? Is that what a lone (Q1, 1, L) indicates?
>
> Someday I'm going to learn not to post in the middle of the night. The
> general idea is to convey that the stated machines are not equivalent
> because new state alone in general is not sufficient to determine machine
> actions. Although on consideration, you might be creating an equivalent
> machine at the cost of exploding the number of states upwards -- I'll have
> to think about it more when I have less cotton in my head.
>
What a difference a day makes. Okay let's try this again....
You're defining a Turing machine as a 6-tuple
(Q, X, q0, qa, qr, d)
with
Q a finite set of states
X a FSM transition function Qx{0,1} --> Q
q0, qa, qr SUBSET Q, the sets of starting, accepting and rejecting states
(presumably such that Q = q0 U qa U qr)
d a TM reconfiguration function Q --> {0,1}x{L,R}
With the semantics that the transition function gives you a new state and
applying d to that state gives you the next machine instruction.
So in essence, your TM transition function is
d': (Qx{0,1}-->Q) --> ({0,1}x{L,R})
a function that maps functions to machine instructions (for a deterministic
TM; otherwise it maps functions to the powerset of such instructions).
And the question is, is this equivalent to
d_0: Qx{0,1} --> Qx{0,1}x{L,R}
It seems to me that for a state Q, the triples (Q, 0, R), (Q, 0, L), (Q, 1,
R) and (Q, 1, L) are all possible right-hand sides to d_0; whereas Q must
unambiguously determine one of these in case of d. So to allow for all the
other "equivalent" configurations, d must be considerably larger as a set
than ran(d_0), as must Q in your TM description (to allow for extra states,
potentially four for every state you would have in my description). So no,
not equivalent.
But I'm going to play a hunch here and say that there probably is a morphism
between d_0 and d', if not an ISOmorphism. And it will probably be very
similar (if you impose a FSM onto the state transition part of a TM alone)
to the MDFA algorithm, the algorithm (or class thereof) that finds a
minimal DFA, given a DFA.
If so, that would mean that "your" TM should still be able to achieve all
the configurations of "mine" if by a somewhat longer route, making them
indeed equivalent and both TMs.
Which of course has no effect on the question at hand. A TM (no matter what
form) is fully described in its behavior by its transition function, not by
its tape length. Any language or mechanism that can be used to implement
such a function is then by necessity (and definition) Turing-complete.
Programmer Dude
>> Good style is a matter of opinion.
>
> Not as much as people think. A large part of good style is to follow
> the conventions developed over the years by the members (especially
> the experts) of the community. Good style is not just for pleasure.
Agreed. However, there is not necessarily a consensus on exactly what
good style is. Some think it's one thing, other think it's another.
That's what I mean about opinion. I'm not suggesting it a random or
personal choice thing.
I mentioned use of parentheses previously, and it's a good example.
Some folks opine that "unnecessary" parentheses are Bad Style and
decrease clarity, while others feel they are Good Style and aid clarity.
Casts can be viewed similarly as self-documenting and indicating that
the programmer is acting intentionally.
>>> In fact, you have altered your C program so that it will fit with
>>> the type system and semantics of C++.
>>
>> Nevertheless, they continue to be 100% legal C programs.
>
> Sure, but they are no longer idiomatic.
Now we're *really* getting into matters of opinion. Some very good
programmers reject the idea that idiomatic is a Good Thing. Some
would opine that idiomatic is Bad Style.
> Good style is mainly about respecting programming idioms of the
> community.
I disagree. Good Style is about writing programs that are correct,
clear, self-documenting, as portable as they need to be, as modular
as they can be, as cohesive as possible, and a lot more.
The "programming community" is just a bunch of people with opinions,
and many of those opinions are in direct conflict with each other.
(I might point out that most innovation does not come from following
the pack.)
>> Hard to imagine a good design that would require it (because who
>> can *count* on the effect of adding a number to a character).
>
> Chars in C are not characters, just small integers.
Of course. But my sense of Good Style specifies their use only to
contain characters. I don't use them as "small integers".
>> Good designs don't mix types.
>
> So you are saying that this is bad style :
>
> unsigned int counter;
> ...
> counter += 2;
>
> Could you please tell me what you would do in this situation, i.e.
> how would you add 2 to this counter represented as an unsigned int.
To my knowledge, neither C nor C++ have a problem with that, so no
cast is required. But (IMO) truly Good Style might suggest you
indicate you are in full knowledge of the situation:
unsigned int counter = 0;
counter += 2U;
And *truly* Good Style would reject that "magic number", 2, and
suggest this:
const unsigned int INCREMENT = 2U;
unsigned int counter = 0;
counter += INCREMENT;
And that's pretty much how I'd do it in production code. As I think
I've said, to me, Good Style means extremely explicit code.
>>> You could also not use getchar() and friends to read characters.
>>
>> You can if you read them into ints (which you need to do to detect
>> EOF, anyway)!
>
> But then you probably want to put the non-EOF result in a character
> string. If I understand you right, you can't do that without having
> a badly designed C program, since it would mix different types.
Well, usually when I want to read strings, I read strings, not chars.
And I don't often do work that takes input a character at a time. And
it's even more complicated, because I use a set of typedefs that allows
the code to be compiled for ANSI or Unicode.
But, caveats aside, sticking integers into a character string does
require being explicit, and I might well choose to use a cast at that
point.
>> I prefer that it does, because it alerts me to possible errors in
>> design. I don't use C much anymore, but if I did and used a C compiler,
>> I'd be looking for an option to turn that stuff on.
>
> I see it exactly the opposite way. By forcing the programmer to put
> in casts in these situations in order to avoid warnings, some subtle
> hidden errors may persist.
As I said before, that hasn't been an issue, but then I tend to be a
pretty careful designer and coder.
> In addition, the compiler would force me to use non-idiomatic C,
> which is even worse.
You're absolutely entitled to your opinion. Allow me mine.
CBFalconer
> Robert STRANDH wrote:
>
> >> Good style is a matter of opinion.
> >
> > Not as much as people think. A large part of good style is to
> > follow the conventions developed over the years by the members
> > (especially the experts) of the community. Good style is not
> > just for pleasure.
>
> Agreed. However, there is not necessarily a consensus on exactly
> what good style is. Some think it's one thing, other think it's
> another. That's what I mean about opinion. I'm not suggesting it
> a random or personal choice thing.
... Vicious snippage ...
Good style is what has been found, for any particular programmer
or group of same, to minimize errors and maximize clarity.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Arthur J. O'Dwyer
SPOILER FOLLOWS, for those who care.
(!!!!!!!!!!!)
Well, I finally asked a real-life CS professor (Steven Rudich)
about this puzzle, and he gave what looks like a solid answer.
That answer was: NO. Even allowing unbounded recursion, C is
not Turing-complete. Here's an outline of his informal proof:
Suppose we write our program as a bunch of (mutually recursive)
procedures:
void foo ( takes a fixed number of arguments )
{
perform some deterministic action
maybe call some other procedures
perform some deterministic action
}
void bar (takes a fixed number of arguments )
{
perform some deterministic action
maybe call some other procedures
perform some deterministic action
}
...
All these procedures can be transformed into one (gigantic)
procedure by mechanical means. So we now have our entire
program expressed as:
void Program ( takes a fixed amount of information )
{
perform some deterministic action
maybe call Program recursively
perform some deterministic action
}
So what we do is, we make a table. Down the left-hand column of this
table, we put *all* *possible* *inputs* to Program. That is, all possible
parameter values that we could possibly pass to Program. (We can without
loss of generality assume that the program's input via "stdin" is coming
from a global variable somewhere, and include it in Program's "state
information.") Since the amount of information we can pass to Program is
bounded, there will be a finite number of entries in our table.
In the right-hand column, we put a 1 if *for* *that* *particular*
*input*, Program will *not* make any recursive calls to itself. Since
Program is completely deterministic, we can always determine this.
Call these inputs (that get 1's) the "base case."
Then, for any other input where Program *only* makes calls to "base case"
states, put 1's in those table rows. And for all inputs where Program
only calls *those* states with 1's, put 1's in *those* table rows. And on
and on...
Eventually, this procedure will terminate, because there are only a finite
number of table entries to begin with. Put 0's in the rows that still
don't have 1's in them.
Now, all the '1' entries will terminate after a finite amount of time.
All the '0' entries won't; they're the infinite loops and infinite
recursions.
So we've just finished constructing a table that tells us, directly, for
*which* *inputs* our Program program *halts*! And we've done it in the
general case. Which means we've just solved the "halting problem" for
this language.
Since one *can't* solve the halting problem for a Turing machine, but
one *can* solve it for the language we wrote Program in, that language
*must* not be Turing-complete.
Q.E.D.
It's a very neat proof, in which I can't find any holes. So the
question is finally answered. Now I can think about something else.
:)
-Arthur
Programmer Dude
> That answer was: NO. Even allowing unbounded recursion, C is
> not Turing-complete. Here's an outline of his informal proof:
Interesting. However, I don't follow why C would be different from
any other language.
Ben Tels
> Well, I finally asked a real-life CS professor (Steven Rudich)
> about this puzzle, and he gave what looks like a solid answer.
> That answer was: NO. Even allowing unbounded recursion, C is
> not Turing-complete. Here's an outline of his informal proof:
[...]
> So what we do is, we make a table. Down the left-hand column of this
> table, we put *all* *possible* *inputs* to Program. That is, all possible
> parameter values that we could possibly pass to Program. (We can without
> loss of generality assume that the program's input via "stdin" is coming
> from a global variable somewhere, and include it in Program's "state
> information.") Since the amount of information we can pass to Program is
> bounded, there will be a finite number of entries in our table.
>
> In the right-hand column, we put a 1 if *for* *that* *particular*
> *input*, Program will *not* make any recursive calls to itself. Since
> Program is completely deterministic, we can always determine this.
> Call these inputs (that get 1's) the "base case."
>
> Then, for any other input where Program *only* makes calls to "base case"
> states, put 1's in those table rows. And for all inputs where Program
> only calls *those* states with 1's, put 1's in *those* table rows. And on
> and on...
>
> Eventually, this procedure will terminate, because there are only a finite
> number of table entries to begin with. Put 0's in the rows that still
> don't have 1's in them.
>
> Now, all the '1' entries will terminate after a finite amount of time.
> All the '0' entries won't; they're the infinite loops and infinite
> recursions.
Program 0:
int main(int n)
{
while (1);
}
This accepts a finite number of inputs (those between (-maxint - 1) and
maxint), is fully deterministic and makes no recursive calls ever so every
case is a base case and is decorated with a 1 in your table. At the end of
your algorithm, for every input there is a 1 in the table -- the program
ends in a finite amount of time for none of them.
Program 1:
#include <stdio.h>
int rec(int n)
{
static int M = 0;
if (n == 0)
{
M = 2;
}
else
{
for (M = n; 0 < M; M--)
{
printf("%d\n", (M - 1));
rec((M - 1));
}
}
}
int main(int c)
{
printf("Enter input: ");
scanf("%d", &c);
c = (c != 0) ? 1 : 0;
rec(c);
return 0;
}
In this case, the program is also completely deterministic. For input 0, it
enters a base case without recursion, terminates. For all other input, it
enters a case there no other recursive call is made than to the base case.
These cases are marked with a 1 in your method -- they do not terminate in
finite time.
> So we've just finished constructing a table that tells us, directly, for
> *which* *inputs* our Program program *halts*!
More or less....
> And we've done it in the
> general case.
Yes....
> Which means we've just solved the "halting problem" for
> this language.
No. This is not the halting problem. The halting problem is the decidability
of the language {<M,w> | M is a Turing machine and M accepts w }. In other
words, constructing a Turing machine that, for every Turing machine,
decides whether that Turing machine halts for a given input. The reason
that problem is undecidable is that a TM has no way of determining whether
a general TM will halt for a given input except for running that TM on the
input and waiting to see if it ever halts. That is not the same problem as
with your method (in which the program is not a variable but a constant).
Also, you might want to consider that you have, for your method, done
something that nobody has ever done before -- namely, adorned a programming
language (or program) with the ability to make logical inferences about a
program (such as determining what sorts of cases will be called in matters
of recursion). That may be possible in the limited case you describe, but
so far it has not proven possible in general (the limitation being that of
the completeness of first-order logic).
> Since one *can't* solve the halting problem for a Turing machine, but
> one *can* solve it for the language we wrote Program in, that language
> *must* not be Turing-complete.
I would like to see the program that makes said determinations. I'll buy
that you can do it on paper, but I'd like you to show me the program that
does it in the computer.
> It's a very neat proof, in which I can't find any holes. So the
> question is finally answered. Now I can think about something else.
You might want to ask this professor whether or not it bothers him that he
is claiming that a language such as you describe is not only not
Turing-complete, but by necessity more powerful than a Turing machine
(since it can solve the halting problem, according to him).
programmerguy
> The other day, I had a debate with a coworker about the usefullness of
> Java. I didn't think that Java has any usefullness especially compared
> to C/C++. So what are the advantages of one over the other? Why would
> someone choose Java, for example?
Using Java Foundation Classes creating a GUI (that works on any
platform) is very easy. Using C++ creating a GUI is a nightmare,
unless you use some proprietary bastardization of C++ such as Visual
C++
Programmer Dude
> Using Java Foundation Classes creating a GUI (that works on any
> platform) is very easy.
Writing one that doesn't look like crap, however,.... less easy. ;-)
Arthur J. O'Dwyer
Whoops. Good catch. However, the fix is trivial (once you see it, which
took me several seconds). Your objection boils down to: How can we tell
whether a given non-recursive, fixed-size program will terminate in finite
time? IOW, how can we tell whether a given FSM terminates in finite time?
This is trivial (just watch the machine for size_of_machine cycles; if it
repeats a state, then (since it is deterministic) it will cycle forever;
otherwise, it will have already halted).
So I messed up the condition in my summary of the proof; but your
objection doesn't stand up under scrutiny. Still, thanks for the
clarification.
> Program 1:
>
> #include <stdio.h>
>
> int rec(int n)
> {
> static int M = 0;
>
> if (n == 0)
> {
> M = 2;
> }
> else
> {
> for (M = n; 0 < M; M--)
> {
> printf("%d\n", (M - 1));
> rec((M - 1));
> }
> }
> }
>
> int main(int c)
> {
> printf("Enter input: ");
> scanf("%d", &c);
> c = (c != 0) ? 1 : 0;
> rec(c);
> return 0;
> }
>
> In this case, the program is also completely deterministic. For input 0, it
> enters a base case without recursion, terminates. For all other input, it
> enters a case there no other recursive call is made than to the base case.
> These cases are marked with a 1 in your method -- they do not terminate in
> finite time.
Ooh, a much better objection! Here, the omission is in the "preliminary"
step of the proof, in which we "collapse" the C program into a single
recursive procedure "Program." As part of that "collapsing," all static
variables (local and global) must be incorporated into the state of the
procedure. How exactly to do this escapes me at the moment. I'll think
about it; it's a very good point.
> > So we've just finished constructing a table that tells us, directly, for
> > *which* *inputs* our Program program *halts*!
>
> More or less....
>
> > And we've done it in the
> > general case.
>
> Yes....
>
> > Which means we've just solved the "halting problem" for
> > this language.
>
> No. This is not the halting problem. The halting problem is the decidability
> of the language {<M,w> | M is a Turing machine and M accepts w }. In other
> words, constructing a Turing machine that, for every Turing machine,
> decides whether that Turing machine halts for a given input.
(Except for your second objection,) the proof would produce such a
machine.
> The reason
> that problem is undecidable is that a TM has no way of determining whether
> a general TM will halt for a given input except for running that TM on the
> input and waiting to see if it ever halts. That is not the same problem as
> with your method (in which the program is not a variable but a constant).
The preliminary step and the construction of the table can be done
mechanically (i.e., by a Turing machine). Hence, the variable-ness
of the program is not an issue.
> Also, you might want to consider that you have, for your method, done
> something that nobody has ever done before -- namely, adorned a programming
> language (or program) with the ability to make logical inferences about a
> program (such as determining what sorts of cases will be called in matters
> of recursion). That may be possible in the limited case you describe, but
> so far it has not proven possible in general (the limitation being that of
> the completeness of first-order logic).
Obviously. That's why the halting problem is provably unsolvable for
Turing-complete languages. And since we've just solved it for this
language, this language must *not* be Turing-complete (else we'd have
a contradiction).
> > Since one *can't* solve the halting problem for a Turing machine, but
> > one *can* solve it for the language we wrote Program in, that language
> > *must* not be Turing-complete.
>
> I would like to see the program that makes said determinations. I'll buy
> that you can do it on paper, but I'd like you to show me the program that
> does it in the computer.
First, you show me a Turing machine program that multiplies two
unary-notation positive integers on tape. :)
Point being: as long as you accept it on paper, I don't see why I should
have to struggle through the technical aspects of producing such a program
in any particular concrete language. If you can't write such a trivial
algorithm, you shouldn't expect me to write a non-trivial program
essentially from scratch. (I don't doubt you *could* write such a
program, given enough time; but you don't want to waste the time, do you?
Neither do I.)
> > It's a very neat proof, in which I can't find any holes. So the
> > question is finally answered. Now I can think about something else.
>
> You might want to ask this professor whether or not it bothers him that he
> is claiming that a language such as you describe is not only not
> Turing-complete, but by necessity more powerful than a Turing machine
> (since it can solve the halting problem, according to him).
Solve the halting problem *for* *this* *language* (i.e., one as powerful
as C). This is nothing new; I believe Hofstadter has solved the halting
problem for FLoop. It is the halting problem for *Turing-complete*
languages that was proven unsolvable.
Point being: That is a proof by contradiction. The whole point is that
this language is *not* T/C; thus, it can be solved mechanically by a
Turing machine.
-Arthur
Ben Tels
> Writing one that doesn't look like crap, however,.... less easy. ;-)
Mja, but that's not a Java-specific problem -- you get that with ANY
language.
Programmer Dude
> Obviously. That's why the halting problem is provably unsolvable for
> Turing-complete languages. And since we've just solved it for this
> language, this language must *not* be Turing-complete (else we'd have
> a contradiction).
I had understood that The Halting Problem proved that algorithms in
general cannot be universally proven to halt. The point being that
there is no process guarenteed to analyse whether another process
will halt.
Your proof (and it would seem to apply to any language) suggests that
a language cannot construct an algorithm that does not halt. I find
this a difficult claim to accept.
> Point being: as long as you accept it on paper,...
I'm not at all sure I accept it on paper. ;-)