C is not Turing-complete (2018)

9 pointsposted 13 hours ago
by xx_ns

22 Comments

rgmerk

11 hours ago

If we're going to have this argument, are we allowed to read/write to external storage? That would seem to me to circumvent the bounds of pointer address space.

The interface to the external storage only needs bidirectional sequential access rather than random access, so we don't even have to worry about the disk addresses becoming too large for the addressable internal memory.

eminent101

10 hours ago

> are we allowed to read/write to external storage?

They did restrict the scope of their article to the standard only:

"This is an argument about the specification of C, not any particular implementation."

I don't think the spec has any representation of external storage in it.

dpassens

10 hours ago

FILE* is defined by the standard.

zabzonk

10 hours ago

as all programming comes down to pointer twiddling, either under or over the hood, is any language turing complete?

tromp

10 hours ago

Sure; one of the simplest languages possible, the binary lambda calculus [1] is Turing complete. It has no pointers, no variables, and no data type sizes. Only functions (from functions to functions). Everything else must be built out of functions.

Brainfuck with an unbounded tape length is similarly Turing complete.

I think less esoteric languages like Haskell and Scheme qualify too.

[1] https://www.ioccc.org/2012/tromp/hint.html

zabzonk

10 hours ago

but under the hood (the implementation of an actual programming language) it is all pointers - not?

tromp

10 hours ago

The article admits that real machines have bounded memory, the argument is about language specifications only.

netik

11 hours ago

not sure if this matters?

Brian_K_White

7 hours ago

It matters in the way all academmic exploration matters.

Which is to say it doesn't matter if it matters.

Or rather, you can say it matters or not depending on your own personality and capacity for intellectual curiosity.

If all you care about is can I eat it or fuck it, then it doesn't matter. The limits of c match the limits of the hardware, and so you can never run into them. You can express anything the hardware could do. Except, the only way I can say "it doesn't matter within this scope, because of this scope" is because someone at least thought about it long enough to figure that out. The question mattered even though the answer came back "don't worry about it", because that answer matters.

It matters, or rather it may matter (you or someone has think about it for a while to find out), if you would be one of the people who helps understand the current world and helps design the next world rather than just use the world however it happens to exist today.

It may also be that it would matter, but the premis is wrong in some way, which again you can't know without formulating the problem and then thinking about it.

I would say that c with variable pointer sizes or compoundable pointers would still be c, and so if the spec happens to specify the size of pointers, that's just a silly implementation detail that shouldn't be hard coded in the spec and could be ignored or officially revised without changing anything that matters. Like saying the language isn't turing complete because the original proposal has a typo.

Another tack: Someone else pointed out that VA_ARGS gets around it. But that's not magic. VA_ARGS has to be implemented somehow using the tools of the rest of the spec. If one part of the spec says something that the rest of the spec can't do, then the spec is inconsistent. That doesn't mean the language isn't turing complete. It means it might or might not be depending on how you choose to reslove the incosistency.

eminent101

10 hours ago

> not sure if this matters?

Sure, it doesn't directly affect any practical programming tasks to matter in real life... but sometimes it's good to indulge in intellectual curiosity. It sharpens our understanding of how far a language can go, no matter how futile that understanding is. This is HN after all and "anything that gratifies one's intellectual curiosity" is on-topic on HN.

mrkeen

11 hours ago

I was chatting about languages with guaranteed termination as a feature to a C-programmer colleague.

He said "well then they're not Turing-complete" and that was the end of the discussion. Dismissed as 100% useless.

wruza

10 hours ago

Not a CS guy, but afaiu guaranteed termination lowers the automata class to push-down automatons or FSMs, which are definitely not what we’d agree to call general purpose programming languages. In practical terms, they have a computing regime equivalent to that one of regexps of various sorts.

sulam

11 hours ago

I’m sure it doesn’t.

taspeotis

11 hours ago

Good lord that site is not mobile friendly.

can16358p

11 hours ago

It's so bad that I had to abandon the page.

jalk

11 hours ago

At least Firefox Reader View works there without any issues

frizlab

8 hours ago

Curiously (and this is very rare), Safari’s did not.

user

6 hours ago

[deleted]

user

6 hours ago

[deleted]