Re: Which book is better for a begainer to study C language?

On May 14, 11:27 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
"JosephKK"<quiettechb...@xxxxxxxxx> writes:
On Wed, 06 May 2009 15:58:15 +0200, Richard <rgrd...@xxxxxxxxx> wrote:

Chris Dollin <chris.dol...@xxxxxx> writes:

It means it can compute anything computable (by a Turing machine or one
of its many equivalents). What it means in practice is more like "doesn't
have crippling theoretical restrictions"; if I recall correctly, matching
regular expressions doesn't require TC, so REs alone don't make a powerful
enough programming language.

I would not be too sure of that.  Backus-Naur Form is Turing complete
is it not?

No.  BNF describes context free grammars which define the languages
recognised by push-down automata.  This is a larger set than the
regular languages recognised by REs, but is strictly smaller than the
set of languages recognised by Turing machines.

 And no possible RE system is not representable in BNF.

I dont even understand that. With any language I have used before I
could write my own RE parser if necessary.

It is an attribute of the language, not one of the parser.  I have yet
to meet a language (expressed in a LR script) that i could not write a
LALR(1) parser for.  This includes C, C++, BASIC, ALGOL, FORTRAN,
COBOL, Ada, Pascal, FORTH, APL and every assembler i have seen.  I
have heard reports that early FORTRAN and COBOL versions were not
Turing Complete, I do not know myself.

Tiny bit of on-topicness: neither C (nor C++) are LALR(1).  They can
be fudged with a bit of fiddling so you can squeeze them though
automatic systems like YACC, but they are not technically LALR(1).

Its been a long time, but I suspect FORTRAN is even worse.

--
Ben.

And we've now gone from "what the hell is Turing completeness" to LALR
(1) grammars without actually explaining what a Turing Machine is.

In the simplest terms, a Turing Machine is something with arbitrarily
large amounts of memory (if you can't hit the upper bound, it's large
enough), that can do additions and can branch execution conditionally.
Essentially, if it can do increments, GOTOs, and IFs, it's a Turing
Machine. (This is _not_ an exact definition, but should be "good
enough").

A Turing Complete language is one in which you can express (and
compute) anything that you could do with a Turing Machine. Most modern
programming languages aim at simulating a Turing Machine with loads of
syntactic sugar. As in, a while loop is essentially a formalization of
"if something, goto top of loop", a for loop is a very specific case
of a while loop, etc etc.

Church's Lambda calculus is based on recursive functions, and the idea
that mostly "anything" can be computed as the composition of recursive
functions. For example, you can do x + y as: "if x = 0, return y, else
return (--x) + (++y)", and then build x * y on top as "if x = 1,
return y, else return (((--x) * y) + y)". The Church-Turing thesis
later proved the equivalence between Turing Machines and Lambda
Calculus. That is, what can be computed with one can be computed with
the other. LisP is basically an implementation of sugared-up Lambda
Calculus.

Also, all useful programming language are Turing Complete (some, or
perhaps most, markup languages, like HTML, CSS, etc etc are not).
Turing Completeness, when referring to actual languages you're liable
to use, is only useful when it's actually surprising: POV-Ray's SDL is
Turing Complete, whereas VRML is not. TeX is Turing Complete, versus
HTML, which is not.

Directly on topic, in my mind the question of whether C is a newbie-
friendly language can be answered thus: "it's a brilliant language if
you want to learn how computers work, it's crap if you want to learn
how to program". If you want to know about computers, dealing with
pointers, having absolutely no safety nets around buffer overflows,
etc. are all features. If you want to learn how to program, you
probably want a language that lets you worry about the logic rather
than fussing over the computer's innards (at least just yet).
Personally, I'd suggest Python (yes, indenting delineates blocks, but
you'd likely indent the code like that anyway), some academics would
lead you towards Scheme (which is a LisP dialect).
.

Relevant Pages

  • Re: LSP and subtype
    ... > Only if one defines software as a Turing program. ... What is the class of problems solvable using UML? ... the language of physics cannot describe. ... > multiple responsibilities; ...
    (comp.object)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... "Peter Olcott" wrote in message ... |> So where are we going to find a common language, ... Turing didn't. ... | before I could hope to address it on the same Turing Machine ...
    (comp.theory)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... "Peter Olcott" wrote in message ... |> So where are we going to find a common language, ... Turing didn't. ... | before I could hope to address it on the same Turing Machine ...
    (sci.logic)
  • Re: a language is a language
    ... but to most people "programming language" ... Turing Machines don't require infinite storage. ... you can run any Turing Machine program that terminates in S ...
    (comp.programming)
  • Re: What, exactly, is Apples iPod business model?
    ... It isn't a programming language ... You can simulate any special-purpose Turing Machine with Cobol or any ... "Computer science" became an attempt to separate theory from practice ...
    (comp.sys.mac.apps)