C is not Turing-complete (2018) | Hacker News Reader

C is not Turing-complete (2018)

memo.barrucadu.co.uk

10 pointsxx_ns20 comments

Didn't we have the this important debate (c.f. [0]l recently? I thought it was concluded that you can use VA_ARGS or addressless memory like registers to escape the tyranny of finite pointers.

[0] https://en.wikipedia.org/wiki/How_many_angels_can_dance_on_t...

C is Turing complete

https://dotat.at/@/2024-08-02-turing-c.html

https://news.ycombinator.com/item?id=41138599

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.

> 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.

FILE* is defined by the standard.

Thanks! I stand corrected.

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

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

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

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

not sure if this matters?

I’m sure it doesn’t.

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.

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.

> 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.

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.

Good lord that site is not mobile friendly.

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

At least Firefox Reader View works there without any issues

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

Reply on news.ycombinator.com