Skip to main content
41 votes
Accepted

Is C actually Turing-complete?

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here. In most ...
Gilles 'SO- stop being evil''s user avatar
40 votes
Accepted

Why is C's void type not analogous to the empty/bottom type?

In C, void is used for multiple unrelated things. Depending on what it's used for, its meaning may be a unit type, an empty type, or something else. When ...
Gilles 'SO- stop being evil''s user avatar
25 votes

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. Not quite. C ints are machine-word-sized and ...
Alexey Romanov's user avatar
17 votes

In C, why limit || and && to evaluate to booleans?

An operator can be described in terms of three things: The accepted range of values (type) of each of its operands Its behaviour The possible values (type) of its result The simplest "or" ...
IMSoP's user avatar
  • 501
16 votes

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines. For comparison, consider the word RAM model. In this model, memory is divided ...
Pseudonym's user avatar
  • 22.3k
16 votes

automatic memory allocation

There are three types of memory in C: static (global variables), automatic (stack) and dynamic (heap). All three are needed to express programs conveniently and efficiently. Why static memory is ...
Gilles 'SO- stop being evil''s user avatar
14 votes

Is C actually Turing-complete?

C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic ...
feersum's user avatar
  • 313
13 votes
Accepted

How are extremely large integers stored and implemented in programming languages?

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$. The basic idea is simple, you represent ...
Vincenzo's user avatar
  • 3,317
11 votes

Why is C's void type not analogous to the empty/bottom type?

The name “empty type” is perhaps confusing. What this means is, as you say yourself, the type contains no values. The “empty” refers not to any individual values of the type, it refers to the type as ...
leftaroundabout's user avatar
11 votes
Accepted

How does the linker know where to look for a function implementation in C++?

The compiler compiles from a .cpp file to an object file (.o) with the binary code. The linker combines all of the object files together into a single binary. So, the linker doesn't need to know which ...
D.W.'s user avatar
  • 162k
9 votes

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Is this correct? I haven't seen anyone else claim that Python compares ints in log time. No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can ...
Tom van der Zanden's user avatar
9 votes

How does the linker know where to look for a function implementation in C++?

It is the linker's job to link the function declaration to its implementation This is not true. This is the compiler's job. Essentially the declaration (I'm assuming you mean the prototype, as in <...
slebetman's user avatar
  • 699
8 votes

In C, why limit || and && to evaluate to booleans?

Edit: After re-reading the question and wovano's comment I think my answer below misses the point because the suggestion to return the non-zero operand or zero if there isn't any would not be overly ...
Peter - Reinstate Monica's user avatar
6 votes

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Although this may seem like a trivial point, your first sentence is incorrect. The functions are not equivalent. To make them equivalent, the C function should use GMP (or similar) to implement ...
Steve Jessop's user avatar
6 votes
Accepted

What are pointers in low-level language like C

In general, a pointer is a variable which holds the address of a variable. You can use https://godbolt.org/ to find out the assembly equivalent of a pointer. For example, ...
user123's user avatar
  • 1,112
5 votes

Why is the address-of operator in C/C++ represented with the "&" symbol?

Because B did! A user on software engineering.sx contacted Ken Thompson: From: Ken Thompson c copied from b so & and * are same there. b got * from earlier languages - some assembly, bcpl and i ...
Pål GD's user avatar
  • 16.7k
5 votes

In C, why limit || and && to evaluate to booleans?

The operand of if, while, etc. isn't limited to integer types, but will also work with floating-point or pointer types. For a ...
supercat's user avatar
  • 1,261
4 votes
Accepted

What is standardization in computer science?

A standard for a programming language is a document defining the syntax and semantics for that language. Usually, for real-world languages, this document involves a (hopefully) precise description in ...
chi's user avatar
  • 14.6k
4 votes
Accepted

Hash multiple integers directly using FNV-1a

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing. The core step that offers mixing of the bits is multiplication by ...
D.W.'s user avatar
  • 162k
4 votes
Accepted

What does the following algorithm approximate? (Assume m>1,ϵ>0)

By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (...
integrator's user avatar
  • 1,110
4 votes
Accepted

does a non-terminated string count as a token in c?

No, in C unterminated strings are not tokens. The C language definition precisely describes what a token is; among other things, they include (complete) string literals and a fallback category of "...
rici's user avatar
  • 12.1k
4 votes

How do compilers assure stability?

It happens that compilers contain subtle errors. No blatant errors, because blatant errors would be detected and fixed. A compiler that is itself compiled by a compiler with subtle errors will tend to ...
gnasher729's user avatar
  • 30.5k
4 votes

Are C standard library functions considered part of C programming language

The “C programming language“ is defined by a document that defines the syntax and the semantics of programs, and the C standard library. So both are part of the “C programming language”. However, in ...
gnasher729's user avatar
  • 30.5k
4 votes

How are kernels (and operating systems in general) written in C?

There's a lot to unpack here, but I'll try to keep it as Computer Science as I can. Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel? Yes and no, respectively. ...
Pseudonym's user avatar
  • 22.3k
4 votes
Accepted

Pointers and Dereference Operator

I'm not sure if this is in topic here. Anyway, (*a) in (*a)=(*b) denotes a lvalue referring to the object in ...
Steven's user avatar
  • 29.5k
4 votes

Why is C still the fastest? Critique my take

The OS has virtually nothing to do with the relative performance of languages on benchmarks. You wrote “your code —(system calls) —> the OS —(instruction set) —> the hardware” suggesting you ...
benrg's user avatar
  • 2,157
4 votes
Accepted

Why is C still the fastest? Critique my take

C is fastest because there is nothing preventing it from being the fastest. A CPU always runs machine language. When writing a "fast" program, your goal is to give the CPU the fastest ...
Quitting Due To Antisemitism's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible