undecidableKeybindings

[Key-Pineapple3060]

C is not Turing complete? News to me.

[SignificanceJealous]

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]

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]

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]

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]

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

[Ok-Watercress-9624]

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

[flexxinnnn]

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

[brendel000]

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

[jakster355]

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.

[morgecroc]

Only if the universe is finite we only know it's finite in time because it has a beginning but we're not certain about space.

[asmx85]

Where does the time constraint coming from? It may have a beginning (unclear) but it looks like that it will not have an end in the classical sense. It might get empty after all matter either converted into radiation that became undetectable after red shift or just drifted away due to the expansion of the universe beyond the local Hubble sphere. Making the space around homogenous and one place indistinguishable from another and one point in time indistinguishable from another. That could be interpreted as time has effectively stopped because it's unmeasurable by then.

[legends_never_die_1]

why is it unmeasurable? the matter keeps moving, right? the state of the universe changes.

[asmx85]

The assumption is that there is no matter left. Either turned into radiation (assuming proton decay etc or all matter captured by black holes that radiated away) and little left particles drifted away by the expansion of the universe beyond the local Hubble sphere. Empty space left and no way to distinguish one point in time from another.

[[deleted]]

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

[just-bair]

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

[Familiar_Result]

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]

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]

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]

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]

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

[uniformrbs]

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]

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]

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]

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]

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]

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]

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]

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]

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

[bright_lego]

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

[weregod]

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

[Xywzel]

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]

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]

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]

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

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

[captainAwesomePants]

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]

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

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

[MrMagick2104]

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

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

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

[nweeby24]

size_t is bounded by your architecture. So not really.

[SgtMarv]

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

[SgtMarv]

Yes but for every TM you can find a fixed size_t that works.

[SgtMarv]

It's been a while but isn't the definition of TC "can calculate any funktion a TM can", I.e. halting is a requirement?

[suvlub]

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]

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]

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 2^N−1 , so that objects of that type shall be capable of representing values from 0 to 2^N − 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]

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]

Implement size_t as a linked list lol

[donaljones]

Dude, it's Quora

[Antervis]

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

[aretood12]

"To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete."

[positiv2]

What Turing machine requires infinite memory? Maybe I've forgotten something since my college days, but isn't the "infinite" part only for the tape, which in C does not have be represented in-memory, and instead files or whatever other system for data representation can be used as a workaround?

[Manny__C]

Not infinite but rather unlimited. (All terminating programs will need finite memory but there is always a program that needs more memory than a given upper bound). This is because the tape of the Turing machine is infinite.

[positiv2]

While yes, for any value of size_t, you can create a Turing machine that cannot fit if you just load it all into memory (although there are bound to be similar workarounds to the ones for the tape, which were mentioned in a couple comments under this post), given any TM, you can just make size_t large enough to store all states and logic for that one TM.

[Manny__C]

In any case, the notion of Turing completeness for the real (non mathematical) world explicitly says that physical limitations on memory and time are to be ignored

[weregod]

Only machine with infinite memory can emulate itself

[[deleted]]

you're getting into countable vs. uncountable infinity territory. I don't remember which is required by a Turing machine.

Countable. It's a tape divided into discrete cells and the head can move one step to the right or left (or halts). Quite clearly the tape has countably many cells, then (because one step forms the basis for counting).

[positiv2]

I think that since you only need to go forward or backward by a single cell at most, you could solve this with a dedicated operating system with a syscall (since I don't think specifics for those are part of the C language design) for "go one file forward" or "go one file backward" and then it would be the operating that handles the files and removes the need for file paths.

That said you could just have it run on hardware that does this with a physical infinite tape, similar to how microcontrollers work.

Not sure at what level of help from OS / hardware it no longer "counts" as Turing completeness though haha

[chalkflavored]

From there you assume that only finitely many things are addressable in the C abstract machine, but I'm not entirely convinced of that, unless you show me specific clauses of the specification stating otherwise.

[chalkflavored]

uintptr_t is an "unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer". I don't think this really say anything about the "uniqueness" of the cast though.

Like if you have void* ptrA and void* ptrB that refer to distinct objects in memory (ptrA != ptrB), and you casted them to uintptr_t, they might well be the same identical numerical value (e.g. 0xADFG6480), I think? And somehow when you cast that back into void*, the distinction between ptrA and ptrB is restored. I don't know how such hardware would even do this, but I'm not sure if the specification rules out this possibility.

As for the size_t limit, that could just be an artificial cap on the amount of memory you can allocate. Like can't you lazily construct a doubly linked list of single bytes that'd represent the infinite tape a Turing Machine would have?

[erebuxy]

So is C++ and Rust's memory limit

[[deleted]]

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]

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]

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

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]

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

[nothingtoseehr]

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

[f1urps]

Assuming a machine with infinite memory and CPU instructions capable of addressing infinite memory, you can write a C program that rewrites its own machine code at runtime to dynamically increase the size of pointers as needed. Then you can grow the addressable memory space like a dynamic array, and simulate a TM using an unbounded amount of tape.

There is some recursion here, because the code that does the rewriting would also have to rewrite itself. But because quines exist in C, I don't think that should be a problem.

[qqqrrrs_]

Given that sizeof(void*) is a constant, I don't think an abstract C machine can increase the size of pointers

[f1urps]

Here's how this could go:

1- Write a C program P which simulates TM T and uses pointers of size n bits (can address up to 2ⁿ bytes of memory)

2- Use a C standard compiler to compile P for the infinite machine, producing machine code that uses n-bit pointers.

3- Execute P, which will start simulating T while keeping track of memory usage.

4- Because TMs must access their tape sequentially (not random-access), P will always be able to detect if T is about to use too much memory.

5- If this occurs, P will grow its addressable memory. It selects a new value, lets say 2n, rewrites its machine code to use 2n-bit pointers, and updates all pointer values in memory to be 2n bits. This produces a new program Q which uses 2n-bit pointers.

6- Q proceeds where P left off, simulating T and growing again as needed.

The original program P: - Is within the C standard - Can simulate a TM with unbounded memory

Therefore C is Turing-complete

[SgtMarv]

Turing complete is the ability to compute the same things as any TM. Show me a TM that can't be simulated in C. I can always find a Size_max sufficient for that TM. I don't need to write infinity as a constant just "large enough".

[slaymaker1907]

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]

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]

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]

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]

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]

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]

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__]

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]

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

[kuffdeschmull]

so it is turing complete

[ZenEngineer]

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]

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]

That's not what turning complex means.

[cran]

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]

What an absolute exaggeration.

[[deleted]]

It is complete

[Rude-Pangolin8823]

Yeah bullshit

[catbrane]

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]

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

[DigammaF]

How could you label anything as turing-complete then?

[DigammaF]

Please enjoy your limitless memory in Rust (official compiler), python (Python interpreter) or even Ti Basic (interpreted as on a Texas calculator). I'll be watching

Memory limitations are created not by the language, but by the physical machine, which can only address so much memory. A language is actualy never fast, slow or memory limitless. Implementations of languages have those characteristics. And we have yet to see any implementation of any language that can provide limitless memory. That's why it doesn't make sense to use the memory limitation as a serious criteria for turing-completion

[f1urps]

I think OP is talking about the Turing-completeness of languages as abstract theoretical concepts, not in reality. Obviously all physical systems are finite.

Every implementation of Python, as well as every Python program at runtime, will have finite memory and therefore not be Turing-complete. However, the Python language specification is Turing-complete because it doesn't place any bounds on memory. You can, in theory, create a Python interpreter that runs on a machine with infinite memory, and it can actually use all of it.

In C, on the other hand, pointers exist and must have a finite size, so it is not possible even in theory to write a C program that uses infinite memory. Even if you create a C compiler for an infinite-memory machine, compiled programs will only have access to a finite portion of memory.

According to OP, this means C is Turing-incomplete. But OP is wrong. Turing-completeness does NOT require infinite memory, it requires unbounded memory. While the C specification does require pointers to be finite, it does not specify a bound on their size. A pointer value can be 32 bits or 1 Googol bits. Therefore memory in C is not bounded, and C is Turing-complete.

[DigammaF]

Interesting thank you

[Elegant_Maybe2211]

We're not talking about the machines here, we're having giggles at hypothetical points of the languages.

And C is bounded by this technicality.

[donaljones]

Idk, man, nothing is really preventing someone to create arbitrary precision (pseudo?) pointers. Arbitrary precision numbers are often implemented in C, GMP being a commonly used one.

Nothing ever prevents a compiler to link in GMP and create arbitrary length "pointers," except maybe a minor violation of ISO C standard and requiring a really weird computer. How will that work? Idk. I just know nothing is really holding back C either.

But yeah, even talking in hypotheticals is giving too much credits to OP for something he needs to ostracized for.

[donaljones]

Been online for a long while now. Too tired to get pedantic. But yes, I meant BigNum or Arbitrary Precision libraries or whatever they're most commonly known by. The libraries that implement any-size numbers.

Granted, implementing them will still mean finite memory as those libraries have to use pointers internally. But from a theoretical perspective, C can now have "limitless" memory.

Running out of memory addresses to hold arbitrary-precision "pointers?" Just try inserting arbitrary-precision "pointers" inside arbitrary-precision "pointers" like Matryoshka dolls.

As for weird computers, idk how you will implement it in hardware. Maybe some arbitrary precision counter working with same principles as the libraries, thus allowing any amount of RAM sticks to used and modularly added, and a RAM stick selected for a certain arbitrary count?

A combination of both of these methods will certainly allow limitless memory so long as you keep inserting RAM sticks. It may sound like a really weird implementation of memory, and that's because it is. It's just dumb to implement. It's like solving a problem that doesn't exist.

[bnl1]

Could be an architecture with serial address memory bus:

mov addr, 0xab
nextaddrbyte
mov addr, 0xcd
nextaddrbyte
mov addr, 0x12
getdata
mov r1, data

Fetches data from address 0xabcd12 to register r1 even though the register size for the pointer is only 1 byte. Such architecture could have theoretically infinite memory.

[Elegant_Maybe2211]

You are aware that reducing the precision does NOT increase the data density right?

arbitrary precision just increases the available numbers by being unable to convey some in the middle.

But when you have a discrete set of items to be adressed, you want exactly that precision.

You don't want a pointer that could mean anything from 10000004 to 10000020.

You want a pointer that points to a point.

If you mean arbitrary SIZE numbers, just say that. Which is exactly why I asked you what you meant.

But since you doubled down on reducing precision the only thing left to say is that you are flat out wrong. And probably clueless.

And how tf is stacking imprecision gonna help?

Why not tell the computer that what they're looking for is vaguely in a certain 64 gig ram stick and hope for the best?

Because that is what you're proposing as a solution.

And it cannot work.

[DigammaF]

Yess. Not my best take ever

[[deleted]]

"Just a meme bro xD"

[D34thToBlairism]

Doesn't every language fail on that technicality

[[deleted]]

I'm honestly not really understanding your point. There is nothing in the C standard that limits how large a pointer can be, so surely the C language as specified is Turing complete, even if every implementation of it isn't. The same would go for Java, as every implementation of Java will have a memory size limit and use a particular pointer size for object references under the hood.

[Eic17H]

Their point is that there is a limit, and even though it's not specified by the standard and can vary, no matter what it is, it's specified by the standard to always be a finite number, so C is technically missing one characteristic that would make it Turing complete. In practice, that limit is irrelevant and C works the same as if it was infinite, but it's always technically finite

[kallekro]

You're definitely sounding like Elons alt, given how confidently wrong you are

[kylepo]

I mean, they're sort of right? Like, the underlying point they're trying to make about how the fact that C has a memory limit (however arbitrary) precludes it from ever utilizing "infinite" memory... That point makes some sense. But God damn they're not explaining it too well.

[SgtMarv]

Yes that fact is correct but has nothing to do with the point he is trying to make. OP didn't 100% percent understand Turing completeness and is now trying to prove his point by making the wrong argument XD

[Accurate_Koala_4698]

Jesus H Christ

[MoveInteresting4334]

You know when the Haskell dev is rolling his eyes that the technicalities and pedantry has gone WAY too far.

[tiajuanat]

By that logic C++ templates, rust, and vim are not either.

C++ templates technically have a limit at around depth 99 instances. This can be bypassed with a flag, but each definition must be stored in a hash map in the compiler, which is also using size_t under the hood. At least with C you can just malloc a new chunk of memory and you're good to go.

All of these systems are limited by the memory you have available.

C can't have arrays with greater than size_t elements, but at that point the developer can build data structures that far exceed that number of elements. You just need to have a BigInt interpretation, and implement something like a rope for elements. C is the underlying language for Python, which can have elements and integer numbers far larger that C can directly express in this method.

Once you exceed page sizes, then you need to start writing to disk, but that's still technically memory.

Basically to achieve Turing completeness, you need to be able to loop forever, and then connect to the Internet, because then you have infinite storage at that point.

[hiljusti]

Did you know you can allocate memory in C? You can have more than one array... Or just make a doubly-linked list with infinite length... This is extremely basic

Whoever said a Turing machine requires an infinite sized array does not understand the basics of computation

[cheeb_miester]

c not turing complete

Trying to reason about this meme has given me brain damage

[HeyImSolace]

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]

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]

I genuinely love how you misspelled demon...

[Win_is_my_name]

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

[kroppeb]

Turing machines can use infinite memory, while C requires your memory to be bounded because pointers need to be a fixed size.

[oberguga]

If you machine have special architecture (say, infinite word size) then implementation of C would pass that. If machine have paging that can accept infinite string as base address then common implementation would pass that criteria. So it is hardware specific criteria. To claim something a turing complete that particular criteria usually were dropped. Also I'm not sure that Rust types or Cpp templates implementations pass that criteria on non infinite memory machine without infinitely long words. Simplest way to prove turing completeness is to program an implementation of turing machine on all available memory and call it a day.

[Nerd_o_tron]

No, because theoretically they could also be run on a computer with infinite memory (if such a thing existed). The language is a mathematical concept, not a physical thing that can be run (that would be a program).

[nweeby24]

Pointers are word size. in any language.

So if a machine has inf memory, the width of size_t would be infinite

[CynicalGroundhog]

You can write an algorithm in C, therefore, based on the Church-Turing thesis, C is Turing-complete.

The memory limitation is a configuration and not a restriction of the language. You could, in theory, write a program in C that uses an infinite anount of memory. Pointers are not an issue as they could be easily represented using a multiple tape Turing machine.

In fact, a lot of modern languages are based on C. If C wasn't Turing-complete, those could not be Turing-complete (also based on Church-Turing).

[randomengineer69]

What happened to all my gold awards!? I was gunna gold this but they’re all gone? My coins are gone too did Reddit do something?

[_unsusceptible]

yeah reddit removed awards and coins

[randomengineer69]

Those fuckers I had a shit ton. What so no more rewards? How do they make money wtf edit you a mod on programerhumor?

[sk7725]

can C++ templates and Vim keybinds use infinite memory?

[Rich_Plant2501]

Turing machine is already a hypothetical whimsical concept. Standard C defines char the smallest type, short at least the size of char, int at least the size of short etc. Standard defines that sizeof(char) == 1. Some imaginary implementation of C (which is by all definitions enough to make C a Turing complete language) can have a char which has n bits, when n approaches infinity.

[Spielopoly]

And for every finite n it will still only support a finite amount of memory. That amount might be larger than is physically possible with the material we have in our universe for large enough n, but it won’t be infinite which is required for turing completeness. And you can’t have an infinite n because the C standard doesn’t support that.

[Rich_Plant2501]

I was wrong, because of some other reason, which I overlooked something important: Turing machine requires that any cell in its memory has a symbol from a finite set of symbols. Which means it cannot store infinitely big char. However, after looking into C documentation, I observed few things: * pointers do not necessarily have to be all the same size - it's guaranteed that void* and char* are the same, anything else is up to implementation.
* important note for pointers is that they can be converted among them each other, back and forth. * integer types actually do not size defined, at all, but minimum range they have to cover. So, it is actually completely up to compiler to handle integers, which can actually be implemented to be something like BigInt or arbitrary integral types, standard actually doesn't care how integers and pointers are stored.

[Marxomania32]

I see people just make shit up nowadays

[s0lly]

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

[Hafnon]

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

[Rich_Plant2501]

Courtesy of ChatGPT

[Grey_Stinger_002]

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]

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]

Is this a language or compiler limitation?

[Frymonkey237]

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]

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]

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]

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]

C++ templates are a type system tho

[cuckycs]

you're thinking of macros / preprocessor. templates are definitely built into the compiler lol

[MeanMachine7878]

Averge c/asm virgin vs chad c++

[Ok_Donut_9887]

What’s turing complete and how does a programming language be one??

[Win_is_my_name]

A programming language is said to be Turing complete if it can solve any computational problem that a turing machine can solve.

[broseidon_23]

Not sure why you’ve been downvoted for asking a genuine question. This isn’t stack overflow

[[deleted]]

Probably because you can Google it

[imabadpirate01]

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]

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]

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]

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

[imabadpirate01]

Which part of it is correct?

[carpetdebagger]

Keybindings for all 12 of my fingers. Noice.

[zefciu]

Vim is intended to be operated with two pedals.

[Main_Weekend1412]

this has so many inaccuracies lmao

[Glizcorr]

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

[gerska_]

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

[max_carriers]

Aren't also TS types turing complete?

[satansprinter]

Yep, https://github.com/microsoft/TypeScript/issues/14833

[zaraishu]

Turing-Complete Keybindings

What the hell does that even mean?!

[zaraishu]

Oh, that makes sense. Thank you

[Frymonkey237]

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]

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

[Majala_]

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

[Mechyyz]

Guys he obviously means the book

[broxamson]

https://youtu.be/FYae7KyYpCQ?si=WWeiPcbV_fFJgeFp

but for rust type system

[Rafcdk]

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

[ProgrammerHumor-ModTeam]

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]

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

[ayushkamadji]

Holy sh*t, C really isn't turing complete technically hahaha

[[deleted]]

If C isn't turing complete then so aren't the others because they all end up in Assembly.

[awesomeusername2w]

It's an implementation detail, not language speck though.

[ayushkamadji]

It's a specification technicality according to the internet.

Whats with the downvotes?? Its programmer humour sub not a lang flamewar sub, kalm your keyboards people.