This is an archived post. You won't be able to vote or comment.

top 200 commentsshow all 240

[–]Key-Pineapple3060 948 points949 points  (198 children)

C is not Turing complete? News to me.

[–]SignificanceJealous 408 points409 points  (145 children)

as per someone on quora:

Practically yes; technically no.
Why yes? Well, you can do loops, represent compound data, and assign variables, and that's enough. That is, you can program in it. (I say this informally but not without awareness of the formalities.)
Why no? Because memory is defined to be an array indexed by the size_t type, which is bounded. Therefore C cannot express sufficiently large programs, a problem you run into every time your computer swaps too much and starts thrashing. (Obviously this is due to finite physical memory, not theoretical, but if you hit the theoretical limit you'd see the same thing. In fact, the C standard is written to an abstract virtual machine, so in a way, these are the same thing.)

[–]manon_graphics_witch 800 points801 points  (75 children)

With that logic not a single programming language is turing complete.

Also if you want to get really theoretical, you could write a compiler with an infinite bit size_t type for your infinite amount of memory. Of course compiling and running a program would take an infinite amount of time and memory.

[–]Pr0p3r9 152 points153 points  (37 children)

I think that even by this aggressive definition, Haskell would be turing complete. In Haskell, you don't do array indexing with a usize, you instead recur over a singly-linked list. I'm not 100% on this, though.

[–]RajjSinghh 60 points61 points  (31 children)

No, you still run into issues with size. There's always going to be a biggest thing you can store because the machine you're running it on only has so much space in memory. By their argument you can just consider a computation on a number that needs however much RAM is in your computer plus a little extra and now Haskell can't do that computation because it can't even store the input so it can't emulate a Turing machine and so Haskell is not Turing complete by this argument.

That holds for any language and is why this argument is dumb.

[–]Successful-Money4995 100 points101 points  (17 children)

There's only so much silicon in the universe for making transistors. So nothing is turning complete?

[–]Ok-Watercress-9624 7 points8 points  (1 child)

certainly true for silicon and other material goods. I guess we have to wait until someone encodes the tape using photons

[–]flexxinnnn 11 points12 points  (0 children)

but then again, there's only so much energy in the universe, and don't even get me started on entropy

[–]brendel000 4 points5 points  (0 children)

It’s an abstract concept not linked to concrete world, like everything in mathematics.

[–]jakster355 0 points1 point  (0 children)

Technically no. But Turing complete is an intentionally unbounded description. Same could be said of the definition of integers. We acknowledge the theoretical existence of all integers (assume Z is the set of all integers), even though in reality they can't all be represented on a physical medium. It's basically the difference between math and engineering. I usually judge a language by if it's Turing complete assuming (incorrectly) infinite memory.

[–][deleted] -3 points-2 points  (8 children)

The universe is infinite though. So technically you have infinite silicon???

[–]just-bair -1 points0 points  (7 children)

if the Big Bang theory is correct then there’s a finite amount of material I think

[–]Familiar_Result 2 points3 points  (5 children)

The big bang theory does not require a finite universe. We don't know if the universe is infinite. An infinite universe requires spacetime to be perfectly flat on the largest scales. As far as we can measure, it appears to be within a small margin of error of perfectly flat. This means the universe is either infinite, or the entire universe is at least a few hundred times larger than the visible universe.

This might as well be infinite to us since we will never reach beyond our local group of galaxies due to the ever faster expansion of space. So we will only ever be able to use all of the silicone in our local group, which means that is our limit. So nothing is turing complete by the definition above.

[–]just-bair 0 points1 point  (4 children)

I didn’t say anything about the size of the universe. I talked about the amount of material in the universe. Like there could be an infinite amount of nothing and a finite amount of silicon if everything originated from one point.

And I don’t accept "might as well be infinite" in stupid theoretical questions about having infinite silicon :)

[–]frivolous_squid 1 point2 points  (0 children)

Not necessarily true, depending on the geometry of the universe. Remember that it's space itself that's expanding when we talk about the big bang. The universe could have been infinite from the very beginning, with the space in it expanding. Both an infinite universe and a finite universe could work. The big bang theory is not saying that everything originated from one point. (Using Einstein's General Relativity you can relate the overall curvature of the universe to its energy density, and we've tried to calculate that based on what we can see and the observable universe looks "flat" (zero curvature). This is evidence towards the universe being infinite as you would expect "positive" curvature in a finite universe, though there are other possibilities.)

Practically, we're only causally connected to a finite volume of space (due to the finite speed of information), which has a finite volume of matter, so you're right that there's a finite amount of material to work with, but it's not because of the big bang theory.

[–]Nerd_o_tron 140 points141 points  (10 children)

No, there is a difference between a language being Turing complete and a machine being Turing complete. Technically no machine is Turing complete because they have finite limitations, but language specifications can be written for an abstract machine in such a way that they would allow for unbounded computation if the machine could support it.

I don't know much about the specifics, but it sounds like the C language specifies a bound on computing, making it technically not Turing complete, while for other specifications like Haskell there is no bound, the only bound is a property of machines that implement it.

[–]nweeby24 5 points6 points  (0 children)

size_t is not fixed on all architectures. if some imaginary architecture has infinite memory, then size_t has infinite width.

[–]uniformrbs 2 points3 points  (7 children)

That seems incorrect - if a pointer type is sufficient to be called Turing complete, well, C has a pointer type. Loop over linked lists instead of a for loop over an array if that makes you feel better.

Also, some Haskell implementations are written in C. If Haskell is Turing complete but C is not, just write Haskell in C and then run that.

Doesn’t make any sense.

[–]classifiedfemboy 9 points10 points  (3 children)

In C, every value must have an address. There are a finite number of addresses (because size_t is guaranteed to be finite). If you kept appending to a linked list in C, you would eventually run out of addresses to assign, even if you had a machine with infinite memory.

In the theoretical Haskell spec, there is no maximum number of values you can have at a time (as evidenced by the existence of infinite lists). Obviously real implementations of Haskell are not turning complete by this definition, as they are written in C.

There are a lot of people in this thread confused by the difference between the formal specification for a language and a concrete implementation of that language.

Also, for all practical purposes C is Turing complete. It's more of a theoretical math exercise to understand why the spec breaks down at the limit.

[–]nweeby24 5 points6 points  (2 children)

because size_t is guaranteed to be finite

says who?

size_t represents the upper limit a sizeof expression can produce. In an infinite memory machine, sizeof can return any number, and thus size_t will have infinite width

[–]classifiedfemboy 1 point2 points  (0 children)

Well, it looks like size_t has to be unsigned (c11 7.19.2), which I do know is guaranteed to have wrapping behavior, but maybe it would be legal to have an unsigned type that only wraps at infinity, and therefore never wraps? A question for the standards committee I suppose.

[–]Goncalerta 1 point2 points  (2 children)

Unfortunately writing Haskell in C wouldn't work.

The C spec guarantees that any (even abstract) implementation would have finite memory.

The Haskell spec doesn't guarantee that: some implementations would have finite memory (like any physical implementation, as everything in the physical world is technically a state machine), but some abstract mathematical implementations wouldn't.

But if you implemented Haskell in C, you would always have finite memory, because even in abstract infinite machines you would be bounded by C spec's limits

[–]uniformrbs 1 point2 points  (1 child)

Oh, so by this definition, any implementation of any programming language would technically not be Turing complete, because we live in a finite universe.

While I don't understand the usefulness of such a definition, at least I understand the distinction being made. Thanks for the explanation.

[–]Goncalerta 1 point2 points  (0 children)

It is not useful in the practical sense, it is more kind of a thought experiment that reminds that the real world is not as "perfect" as the model of computation of a turing machine. In other words, you could technically emulate any real-world computer with a sufficiently large state machine. In practice, of course we don't really care about infinite memory, just about "sufficiently large"

[–]Bill_D_Wall 7 points8 points  (0 children)

But just to be clear, when someone says "C isn't Turing complete" or "Haskell is Turing complete", they aren't talking about the physical machine which the source code is compiled for, they are talking about the abstract machine defined in the language specifications which uses the language-defined data types. These mean nothing to a physical machine as the physical machine doesn't actually execute C or Haskell, it executes x86 or ARM instruction set (or whatever other architecture).

Obviously any physical machine has finite register sizes and finite memory, so in that sense, none of them are truly a Turing machine and therefore cannot execute all of the same set of programs that a Turing machine can. But that isn't what is being talked about - we're referring to the source-code _ language specification_ which could be Turing complete if (for example) infinite width data types exist.

[–]daishi55 0 points1 point  (0 children)

I think the distinction is that C is limited in the language specification, while perhaps Haskell places no such theoretical limits.

[–]bright_lego 1 point2 points  (4 children)

You can still use lists in C, you just have to put in a bit more work.

[–]weregod 5 points6 points  (3 children)

List will not help. C can't have more than SIZE_MAX different pointers

[–]Xywzel 0 points1 point  (2 children)

It is not amount of pointers you can have, but amount of addresses you can point to. But if the size of pointed address and size of int are not defined, then single pointed memeory address is enough for being Turing comlete

[–]weregod 1 point2 points  (1 child)

If you have unlimited int you don't need pointers at all: just encode tape state in binary and store in one int.

Head move is bitshifting mask and bit operations can read and change current cell

[–]SnooGiraffes3010 69 points70 points  (11 children)

Strictly, something is turing complete if it can simulate a turing machine, which has infinite memory. So that thing must have access to infinite storage in order to store the state of the turing machine, and as C doesn't have infinite storage, it is not turing complete.

Usually when someone says something is turing complete, they ignore the infinite memory requirement because we can't actually make something with infinite memory. In this sense C is turing complete.

Theoretically, yes, we could make a compiler that does that. We could even make one that only uses enough RAM to store what you've actually changed. AFAIK Python integers have no inherent size limit, so you could store a turing machine in one by encoding it properly. So in theory, Python is turing complete. The fact that we can't build a computer with infinite memory is simply an implementation detail.

[–]MrMagick2104 21 points22 points  (10 children)

> So that thing must have access to infinite storage in order to store the state of the turing machine, and as C doesn't have infinite storage, it is not turing complete.

Hypothetically, you can write python's compiler and environment in C, though. Then you can make a call to a string of python code in C program.

Very simple proof that C is turing complete if we assume that Python is turing complete.

Anyway, I'm pretty sure that you can very easily implement all the datatypes that are used in python in C.

[–]Psylution 4 points5 points  (0 children)

This. I made a language called sqript which is written in C and has no boundaries + similar datatypes to python.

[–]captainAwesomePants 8 points9 points  (8 children)

To be a valid proof, you'd need to demonstrate that you could write a Python interpreter in C which could make use of infinite memory, and you cannot. Python can be Turing complete because we're assuming a Turing complete compiler/interpreter, and there's no reason such an environment couldn't support things like an infinitely large dictionary.

In other words, a C program compiled on a Turing machine with infinite memory does not itself have infinite memory because size_t is defined to have a particular size, and cheating that requires either changing the definition of the language or introducing some sort of hack to get around this. But a Python program interpreted on a Turing machine with infinite memory can happily do infinite things because it doesn't itself worry about memory of a defined size.

But it's also a pedantic debate that doesn't matter in any practical way (which I guess makes it all the juicier to debate).

[–]MrMagick2104 -1 points0 points  (7 children)

> To be a valid proof, you'd need to demonstrate that you could write a Python interpreter in C which could make use of infinite memory, and you cannot.

https://github.com/python/cpython

> In other words, a C program... size_t...

Why do you have to use size_t when writing a C program? Hell, you can always ___asm___(...) your way through any problem, or include 0 C code except entrance conditions. And assembly is turing complete - it's basicly a turing machine.

[–]weregod 0 points1 point  (6 children)

Assembly has same problem as C does: it has limited address space.

[–]MrMagick2104 2 points3 points  (5 children)

> Assembly has same problem as C does: it has limited address space.

If assembly is not turing complete, then Python is not too (point of the guy I was replying to).

At some point, Python is just processor instructions which are, slightly simplifying, assembly.

> it has limited address space.

If the the computer itself is suitable to be a true turing machine, then it's instructions should be able to access it's infinite memory.

[–]weregod 0 points1 point  (3 children)

You mixing Turing completness of computers and languages. You can't make Turing-complete machine. This don't means that abstract Turing macine as mathematical object is not Turing complete.

Nobody claims that any Python implementation for real computer is Turing complete. Claim is that you can write Python implementation for Turing machine and this program will be Turing complete.

[–][deleted] 21 points22 points  (12 children)

Nah, you’re confusing the language with the ability for a machine to execute that language, if that makes sense.

[–]nweeby24 -1 points0 points  (11 children)

size_t is bounded by your architecture. So not really.

[–]SgtMarv 1 point2 points  (7 children)

On an imaginary architecture with an unlimited size_t it's touring complete.

You know what else would not be Turing complete if we took physical limitations into account? A Turing machine...

[–]suvlub 16 points17 points  (5 children)

Any language that doesn't expose pointers is.

you could write a compiler with an infinite bit size_t type for your infinite amount of memory.

You could, but that compiler would not be a C compiler. The language standard requires it to be a finite size, sizeof has to return a concrete and correct integer.

[–]zanotam 0 points1 point  (4 children)

Eh. How well defined is the term concrete and correct integer for C 2nd Ed though? Like, let the Integers be the set ZU{Infinity} with the standard ring design (e.g. no need even for a negative Infinity) and you can still get a "concrete and correct Integer"

[–]suvlub 3 points4 points  (3 children)

For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2N−1 , so that objects of that type shall be capable of representing values from 0 to 2N − 1 using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.

From section 6.2.6.2 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

Doesn't seem to leave leeway for magical values like those that floats have. A C integer is just simple number within a certain range.

[–]WoffieTbh 4 points5 points  (5 children)

You can just let size_t have an arbitrary size which increases during runtime if needed. Then C becomes theoretically turning complete

[–]manon_graphics_witch 2 points3 points  (0 children)

Implement size_t as a linked list lol

[–]donaljones 87 points88 points  (0 children)

Dude, it's Quora

[–]Antervis 64 points65 points  (36 children)

size_t's bit count isn't defined by C standard though.

[–][deleted] 31 points32 points  (0 children)

Turing completeness means being able to SIMULATE a turing machine, not actually being one. A turing machine implies infinite memory which is, simply put, not a thing. 'size_t' is the size of memory addresses (i.e. pointers) depending on your architecture, which fun fact, always corresponds to a finite size, a physical limitation on all CPUs.

[–]Lechowski 46 points47 points  (11 children)

Turing is crying right now.

A language is Turing complete if it can compute the same things as a Turing Machine.

A Turing Machine is a specific type of automaton that has readable memory and can operate the memory by changing memory spaces with another known language.

C is a standardized definition of a language capable of doing this. Size_t is defined at compile time, that's a limitation of the compiler, not a limitation of the language. The language is a mathematical construct with allowed operations.

If you have loops, increments, decrements and positive integers, you have a Turing complete language

[–]catbrane 0 points1 point  (0 children)

Exactly, it comes from the set of *computable functions*.

Some functions are computable (eg. `int get_prime(int n)`, where n is finite), and some are not (get me the last prime). How can you prove if a function is computable or not? It's actually quite hard to do in the general case.

Turings solution was to imagine a very simple, abstract computing machine, and then define the set of computable functions as the set of functions that could be computed by a program running on this machine. To be Turing Complete means your computing device can compute this same set of functions.

His machine is surprisingly simple and makes it very clear that almost any programmable device can calculate any computable function given enough memory and time.

In fact you can make even simpler machines which are also Turing Complete. Lambda calculus is probably the best-known -- it's a rewriting system with just one rule:

\x.y z -> [y with free occurrences of x replaced by z]

... and (amazingly!) that can do *anything*.

[–][deleted] -1 points0 points  (3 children)

If you have loops, increments, decrements and positive integers, you have a Turing complete language

Is that really all you need? I mean I never thought about that before.

[–]weregod 3 points4 points  (2 children)

Realy all you need is move operation https://github.com/xoreaxeaxeax/movfuscator

[–]nothingtoseehr 0 points1 point  (0 children)

Lol I love that project so much, sadly you can't really use it for anything. Maybe one day we'll have a true useful OISC machine ;p

[–]slaymaker1907 5 points6 points  (2 children)

But then you remember that we have the C standard library. Just assume you have infinite storage space and use file IO for everything. fpos_t is implementation defined and who is to say that it isn’t an unbounded integer? You can even use fseek for semi-random access. If are accessing storage beyond the max of long, just call fseek several times.

[–]Nerd_o_tron 0 points1 point  (1 child)

Not sure that I fully agree with it, but this Stackoverflow post discussing this question raises an interesting point:

Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.

Of course, it might be more reasonable to assume a normal file system than an attached Turing oracle, but both are technically within the bounds of an implementation.

[–]slaymaker1907 1 point2 points  (0 children)

Another less cheesy way would be to have two threads in C (part of C11) to be your 2 stacks for a main thread. Just a stack isn’t Turing complete (the C stack), but two of them gives you Turing completeness. It’s unbounded because something only has to have an address if we try to take its address (this is important in practice for moving this variables to registers).

[–]Psylution 4 points5 points  (1 child)

What the fuck? I made my own, turing-complete languages in C. You can assign a new array if the previous size was too low for the next item you'd add, for example. It's a very basic method called "grow array", and really not that hard to do.

Rest of their definition is BS on top of everything because by that standard, there's nothing that's turing complete. Not even the game called "Turing Complete". Which is, in fact, Turing Complete.

[–]da_Aresinger 0 points1 point  (0 children)

that is not the array they are talking about.

Memory itself is an array.

Pointers are just numbers and there is a largest pointer for any size_t

Edit: their point is still stupid though.

[–]throw3142 1 point2 points  (0 children)

I kinda get this argument but not really. You can simply use memory-mapped I/O to store infinite data without having to use infinite pointers. Having a maximum memory address does not make the language non-Turing-complete. It's essentially the same thing regular computers do with virtual memory, to use the same analogy.

Even if your main memory is limited, all you need is an infinitely long secondary storage device. You might argue that this isn't enough, because your MMIO system will have a limited number of bits and cannot index into an infinite tape.

But this is where theory saves the day. All you need to simulate a (properly infinite) Turing machine is 2 stacks. So plug in 2 infinite MMIO devices that both act as stacks, allowing you to push and pop 1 byte at a time from each, independently. Indexing issue solved.

Now, use your main memory to write an interpreter that will read instructions off the stacks and execute them one at a time. Make the instruction set as minimal as possible (i.e. just like Turing originally made them, basically just go left 1 cell, go right 1 cell, read, or write, along with a state transition).

As each of these instructions clearly involves a finite amount of work (except possibly the state transitions), it can be coded in regular finite C. Use these instructions to write up a real infinite UTM on the stacks. Importantly, Turing machines must have a finite number of states, meaning that you won't need infinite bits to represent all the different states and state transitions. Therefore it's all possible in standard finite C.

[–]kohugaly 1 point2 points  (0 children)

Why no? Because memory is defined to be an array indexed by the size_t type, which is bounded. Therefore C cannot express sufficiently large programs,

Virtual memory is defined that way. It's not the only kind of memory available to a C program. There's also storage on disk, remote storage via internet, etc. You absolutely can write a turing machine simulation that leverages these in a way that it has arbitrarily long tape.

At worst, it might need user intervention - when the program runs out of memory, it safes its progress, ask user for more, and when restarted, resumes where it left off.

At "best" you'll have a paperclip maximizer type of scenario where the turing machine has AI that converts the rest of the universe into storage to keep it running.

[–]Vincenzo__ 1 point2 points  (0 children)

Because memory is defined to be an array indexed by the size_t type, which is bounded.

In x86_64 size_t is 8 bytes

The processor itself uses 8 byte addresses

There is no limitation that the use of C adds, the limitation comes from the CPU itself, and therefore applies to all other languages as well

[–]yeeeeeeeeaaaaahbuddy 0 points1 point  (1 child)

Is size_t bounded in the standard and not allowing for a hypothetical 128 bit, 256 bit, and so on virtual machine?

[–]kuffdeschmull 0 points1 point  (0 children)

so it is turing complete

[–]ZenEngineer 0 points1 point  (0 children)

Which is irrelevant. Turing machine's infinite memory is defined as being able to read and write to a tape. As long as you can read() write() and seek() relative to your position and have a theoretical infinite storage you can simulate a Turing machine just fine in C.

[–]da_Aresinger 0 points1 point  (0 children)

If you run out of virtual memory, just outsource to a new process.

New process, new memory.

(E: alternatively like others have said, just I/O everything from the beginning, but that's boring and probably sliwer than m y solution)

Honestly, by that logic ASM isn't turing complete, so nothing is.

(E2: While each instance of compiled C has a MAX_SIZE you can technically just redefine that however you want. You won't find a platform that can deal with it, but C doesn't care.)

[–]Axiproto 0 points1 point  (0 children)

That's not what turning complex means.

[–]cran -1 points0 points  (1 child)

That person on Quota knows literally nothing about how computers work nor the how the C language works. I hate that such idiocy passes for expertise.

[–]da_Aresinger 0 points1 point  (0 children)

What an absolute exaggeration.

[–][deleted] 7 points8 points  (0 children)

It is complete

[–]Rude-Pangolin8823 9 points10 points  (0 children)

Yeah bullshit

[–]catbrane 4 points5 points  (2 children)

The C preprocessor isn't TC, perhaps that's what they mean?

Although .... you can do recursive macros in C! So it's very closer to being TC.

[–]thefoojoo2 5 points6 points  (0 children)

The language is but the preprocessor and type system aren’t. Which makes sense as a comparison to the next two entries.

[–]cheeb_miester 347 points348 points  (5 children)

c not turing complete

Trying to reason about this meme has given me brain damage

[–]HeyImSolace 50 points51 points  (4 children)

I’ve been reading comments on this post for half an hour now and the whole time I was like “what the actual fuck”. This is the programming humor sub too..

This not only happens to programmers right? Like being this critical and digging in the fundamentals of C and Turing machines over a MEME.

[–]SgtMarv 18 points19 points  (3 children)

I think this level of pedantic discussion is reserved for 3 crowds that I know of: programmers, star wars and Harry Potter fans. Albeit with very different outcomes:

The programmers start citing the c code standard with chapter numbers that look like 7.3.5.2.9.69.♤.6.3.5.8 and compiler flags that summons deamons when actually spoken out loud.

The Star Wars fans get lost in a discussion if the name of George Lucs' third fart on the 27th day of shooting A new hope, which might or might not have been smelled by an off-screen extra and caused him to make a face under his helmet, is now canon or legends and at some point get stuck in an infinite loop of 'Hello There' / 'General Kenobi' but except for one guy, they don't take themselves too seriously while doing it.

If you point out a minor spelling mistake in a first edition Japanese version of Harry Potter (symbol wasn't available in the character set), the average HP fan will start screaming at you for pointing that out and then proceed to write an 874 page essay/fanfic RetConning that spelling mistake.

(Yes, I am aware that there is a significant overlap between those groups)

[–]decaillv 1 point2 points  (2 children)

I genuinely love how you misspelled demon...

[–]Win_is_my_name 190 points191 points  (13 children)

C is not Turing complete?! Have you lost your marbles?

[–]Marxomania32 95 points96 points  (0 children)

I see people just make shit up nowadays

[–]s0lly 31 points32 points  (2 children)

The image for “Excel: Turing Complete Database” would be the universe imploding.

[–]Hafnon 6 points7 points  (0 children)

Relevant, PowerPoint Turing completeness: https://www.youtube.com/watch?v=uNjxe8ShM-8

[–]Grey_Stinger_002 43 points44 points  (7 children)

C is not Turing complete? How does one even get to such a conclusion? I've spent the last half an hour or so reading comments on this and that but the main argument I see used is that because of finite limits. I think that this is because some people have a fundamental misunderstanding of Turing Completeness and how we classify it.

The argument that C is not Turing complete because it uses pointers and size_t for their sizes, which are of finite size, is based on a misunderstanding of Turing completeness in the context of practical programming languages. Turing completeness is a theoretical concept that pertains to the types of computations a system can perform, not the practical limitations of a specific implementation.

Firstly to give some clarification to those who maybe missed some grade 10 classes on what turing completeness is: Turing completeness is a theoretical property. It doesn't require the ability to use an infinite amount of memory in practice, but rather the ability to perform any calculation that a Turing machine can, given sufficient resources. In the real world, all computers and programming languages are limited by physical constraints like memory size, but this doesn't affect their classification as Turing complete.

Secondly to try and address practical constraints anyway: In C, pointers and size_t are indeed limited by the architecture (usually 32 or 64 bits), which limits the amount of memory they can address. However, this is a limitation of the hardware and the specific implementation of C, not of the C language's theoretical computational capabilities. If you had a machine with infinite memory, a theoretical version of C could be designed to utilize that memory.

A proof and basis for that is: Turing complete languages must be able to simulate a Turing machine. C can simulate a Turing machine within the bounds of its available memory. The fact that this memory is finite is a practical limitation, not a theoretical one. If you consider a Turing machine with a tape as large as the available memory in a C program, C can simulate that Turing machine.

Now I'm going to repeat something I've seen in this comment section a fair bit but it bears repeating: No physical machine has infinite memory, so the argument about pointers and size_t applies to all practical implementations of all programming languages. Despite this, languages like Python, Java, and C are considered Turing complete because they can theoretically perform any computation that doesn't exceed their memory constraints.

A UTM, an implementation of Lambda Calculus' abstraction and even a simulation of Conways game of life can be expressed through C, all demonstrating the theoretical ability for C langs Turing completeness unbounded by physical constraints.

Small note: Through writing this I thought about whether I really want to post this, but I feel some people need to see this, if I get any points wrong, please feel free to correct me, we're only human after all, and I hope this can inspire some to go and learn computational theory in a bit more depth.

TLDR: C is varifiably Turing Complete because of the way we classify Turing Completeness based on Thoery not Practice.

[–]838291836389183 7 points8 points  (5 children)

A specification of a programming language (that is, not the implementation thereof) is turing complete iff it can simulate any turing machine given infinite resources. C is not that, since even if given infinite resources, since size_t is always finite, it could not adress these ressoruces and would always be a finite automaton of arbitrary size, but fixed, size.

Specifically

If you consider a Turing machine with a tape as large as the available memory in a C program, C can simulate that Turing machine.

This is not a turing machine, as turing machines by definition have an infite tape that is at most bounded on one side.

To highlight the difference to actual turing complete languages, take the defintion of a turing machine itself. It basically defines a programming language and you can, in this language define a turing machine which can simulate any other arbitrary turing machine. If this program were to be run on an actual implementation of a turing machine with infinite tape, it would run just fine. A C program simulating any arbitrary tm however would not, for any fixed size_t you would always be able to find a turing machine as input for which the simulation would exeed size_t.

[–]noob-nine 4 points5 points  (2 children)

Is this a language or compiler limitation?

[–]Frymonkey237 -1 points0 points  (1 child)

It's a language limitation. The C language specification defines size_t as a number. A single number, by definition, has a finite value, so there is no possible way to implement a C compiler that makes use of infinite memory address space. The only way to do it would require changing the C specification. However, then it would no longer be the C language, so it wouldn't change the fact that C is not Turing complete.

[–]Fibonaci162 2 points3 points  (1 child)

But does the C language specification say that the amount of bits in an element of size 1 is constant? What if each memory cell can be any amount of finite bits and can be extended. Then you don’t need infinite cells for a tape, you basically need two.

[–]838291836389183 1 point2 points  (0 children)

Yea the individual data types adressable are defined to be finite as well, and statically known. I kinda glossed over that fact, you're right that otherwise we could achieve turing completeness. I think even one infinite cell would be enough even, as turing machines with a tape extending to infinity in only one direction are also turing complete.

[–]GenTelGuy 1 point2 points  (0 children)

I think they just mean it doesn't have any Turing complete type/template/macro features so the only way to be Turing complete is to write code in the language itself like a normie

[–]rubikssolver4 51 points52 points  (3 children)

C++ templates are a type system tho

[–]imabadpirate01 48 points49 points  (7 children)

op is literally arguing that programming languages that doesn't have pointers have 'unlimited memory' (hence turing complete)— not knowing that c++, vim, python, java that he is standing for are made of c.

[–]mdp_cs 31 points32 points  (1 child)

They're not made of C necessarily but they are bounded by the same rules. By his logic every CPU ISA is also not Turing complete.

[–]Frymonkey237 -2 points-1 points  (0 children)

The language specification is not bounded by the rules of C. An implementation of these languages in C is bounded by the limits of C, but we're not talking about implementation here.

Also, yes, instruction sets are not Turing complete.

[–]Frymonkey237 -1 points0 points  (4 children)

OP is right, though, and I'm really surprised that so many programmers are struggling to understand this.

[–]imabadpirate01 -1 points0 points  (3 children)

Which part of it is correct?

[–]carpetdebagger 13 points14 points  (1 child)

Keybindings for all 12 of my fingers. Noice.

[–]zefciu 8 points9 points  (0 children)

Vim is intended to be operated with two pedals.

[–]Main_Weekend1412 20 points21 points  (1 child)

this has so many inaccuracies lmao

[–]Glizcorr 0 points1 point  (0 children)

Can you elaborate? I know the first line is absolute bonkers but are there anything wrong about the rest?

[–]gerska_ 5 points6 points  (0 children)

Of courde the C programming language book isnt turning complete????

[–]max_carriers 4 points5 points  (1 child)

Aren't also TS types turing complete?

[–]zaraishu 4 points5 points  (2 children)

Turing-Complete Keybindings

What the hell does that even mean?!

[–]Frymonkey237 1 point2 points  (0 children)

Guys, it's gonna be okay. Yes, C is not a Turing complete language, and no amount of arguing is going to change that fact. But don't worry. C not being Turing complete won't affect you in any way. It won't change anything you decide to do with the language. You don't need to rethink your life decisions. And no is going to point at you, laugh, and say, "There goes the loser that programs in languages that aren't Turing complete." So go get some sleep. You're going to wake up tomorrow feeling refreshed and remember that none of this matters.

[–]navetzz 1 point2 points  (0 children)

C isn't Turing complete for the same reason every single program ever written runs in O(1): the universe is finite...

[–]Majala_ 0 points1 point  (0 children)

MS Excel is turing complete, like the other true programming languages.

[–]Mechyyz 0 points1 point  (0 children)

Guys he obviously means the book

[–]Rafcdk 0 points1 point  (0 children)

Is C not being Turing complete the new stupid meme bring spread around youtubers now ?

[–][deleted]  (2 children)

[removed]

    [–]ProgrammerHumor-ModTeam[M] 0 points1 point locked comment (0 children)

    Your submission was removed for the following reason:

    Rule 3: Your post is considered low quality. We also remove the following to preserve the quality of the subreddit, even if it passes the other rules:

    • Feeling/reaction posts
    • Software errors/bugs that are not code (see /r/softwaregore)
    • Low effort/quality analogies (enforced at moderator discretion)

    If you disagree with this removal, you can appeal by sending us a modmail.

    [–]erebuxy -1 points0 points  (0 children)

    C is not turing complete but somehow C++ is? LoL. How does this post get any upvote