Talk:VoidPtr

the brainfuck interpreter can only access 256 cells, so it doest seem to be turing complete --dragoneater67 talk contribs (mobile) 20:00, 1 September 2026 (UTC)

But VoidPtr can! The BF interpreter is just an example. Basilisk (talk)Basilisk

can you access an infinite amount of cells in a program of finite size? --dragoneater67 talk contribs (mobile) 05:57, 2 September 2026 (UTC)

If you implement system call $6 and $7 to address a theoretical n byte address, yes. System call $4 can be called in an infinite loop to allocate infinite memory and access it in the same loop. Therefore accessing infinite cells in a finite program.

The memory model itself is unbounded. Basilisk (talk) 12:47, 2 September 2026 (UTC)Basilisk

So, more people claim that I need to prove TC by writing an unbounded BF interpreter. I'll do that once I get the compiler to support spec 1.2. Feel free to try that yourself in the mean time, anyone reading this. The main implementation is linked on the page. Basilisk (talk) 13:06, 2 September 2026 (UTC)Basilisk

correct us if we're wrong, but an easier (and more natural) way to prove tc-ness would probably be via reduction to a basic load/store assembly language (perhaps something like 6502, but we're unsure). for example, ? as an operator is used a lot in conjunction with a label, which practically creates a jump-if-zero instruction. that, plus the ability to dereference pointers, should be enough to give this language equivalent power to basic assembly, and therefore turing complete --MarkFan8901 (talk) 06:28, 4 September 2026 (UTC)

if we dereference a pointer froma cell, the pointer will rrmain within the cell's bounds --dragoneater67 talk contribs (mobile) 06:31, 4 September 2026 (UTC)

same thing goes for typical assembly, but that doesn't stop it from being tc. you would need unbounded numbers for unbounded reference, yes, but at the very least voidptr should have the same computational power as assembly --MarkFan8901 (talk) 06:34, 4 September 2026 (UTC)

assembly is a BSM, not TC --dragoneater67 talk contribs (mobile) 06:36, 4 September 2026 (UTC)

also, its computational power varies from instruction set to instruction set --dragoneater67 talk contribs (mobile) 06:37, 4 September 2026 (UTC)

we think for practicality, a language should be considered turing complete if its' only a bsm because of the hardware limit on numbers. technically, yes, assembly is a bsm because you don't have infinite space, but that's just because they're designed to run on computers in the real world, and we can't build a machine with infinite space in real life. if we did have a computer like that, then asm would be tc; the restriction is arbitrary and not confined to the language spec. if we were strict about assembly not being tc, that would also implicate any language which compiles to assembly to not be tc either, which is both absurd and inactionable. therefore we think simply not having unbounded numbers shouldn't make a language turing-incomplete. btw apologies if our tone is rough we haven't yet learned how to make arguments without sounding really angry ,w, --MarkFan8901 (talk) 06:55, 4 September 2026 (UTC)

actually hold on amendment to what we just said, we forgot the discussion leading up to this was about the ability to address infinite space, not about hardware. reconsidering it, since the lang doesn't specify any way to bitshift numbers, you couldn't address arbitrarily large spaces without first having an arbitrarily large number, which would make it bounded-storage. our mistake --MarkFan8901 (talk) 07:02, 4 September 2026 (UTC)

wait Fuck no we're stupid, it does actually have a way to do that, though we still have doubts that that makes it tc. this is tougher than we thought --MarkFan8901 (talk) 07:06, 4 September 2026 (UTC)

okay okay wait we've only just now realized your argument. the spec limits values to bytes, and (presumably) you can only address variables via said bytes, thus making it bounded-storage to 256 cells. unless there's a way to reference cells with values that cross more than one byte, then you couldn't refer to an unbounded amount of memory, thus making it turing incomplete. apologies for all the raffle --MarkFan8901 (talk) 07:13, 4 September 2026 (UTC)

syscalls 6 and 7 can only access the first 2³² bytes, which does not equal to infinity unfortunately --dragoneater67 talk contribs (mobile) 05:44, 4 September 2026 (UTC)

Thank you very much for all that input. In fact, syscall 6 and 7 are only allowed to access 32 bit memory. This however is only due to technical limitations (infinite memory is practically impossible). As I have written, the exact implementation of the syscall is up to the implementation. If you implement 6 and 7 to address 128 or 512 ... memory, you will get that access. Bit shifting numbers is a thing. You can add numbers larger than 1 byte, pass those numbers to syscalls and then get as much memory access as you need. I have a compiler for VoidPtr which compiles to x86_64 assembly (the runtime has a few bugs that's why I haven't published it yet, you can find it on the original repo, it is able to compile all examples).

Apparently the syscalls cause a bit of confusion. I will add more details about the role they play. Now that we have established that VoidPtr is indeed able to access infinite memory in theory, just as I have planned for this language, I would kindly ask to consider adding the TC category back. Basilisk (talk) 12:38, 4 September 2026 (UTC)Basilisk

still not convinced, write a program that infinitely allocates memory and sets the newly allocated bytes to 255 --dragoneater67 talk contribs (mobile) 13:09, 4 September 2026 (UTC)

my point here is, no matter how many bytes syscalls 6 and 7 read, theres still a bound which prevents it from being tc, if it reads 256 bytes, its still finite, if you allow even more, itll still be finite, more major changes are needed to make it tc (like, making the cells themselves unbounded) --dragoneater67 talk contribs (mobile) 13:12, 4 September 2026 (UTC)

By this definition any language would be Turing incomplete. Unbounded cells = infinite memory = impossible. If I say that syscall 6 and 7 can read as much memory as you want, it's the same claim BF makes when saying that you can advance the pointer infinitely to the right or left, which you practically can't because something needs to store the pointer. Turing-complete in section overspecification: "If a language specification requires that the size of some address (for example) be "implementation-dependent but no less than 16 bits" then one can argue that there exists an "implementation" where the size of addresses is unbounded, and that this "implementation" is Turing-complete. (That is, provided that the concept of an "implementation" which can never be implemented on a real computer is unproblematic.)" If I allow syscall 6 and 7 to access infinite memory in theory then that makes VoidPtr TC. Basilisk (talk) 13:29, 4 September 2026 (UTC)Basilisk

the problem with your argument is unlike brainfuck where the pointer can be unbounded, its impossible to make syscalls 6 and 7 unbounded, the spec basically says that they read n bytes, and if you set n to infinity, then itll just never stop reading, if its not infinity, then the amount of memory that is actually available becomes bounded --dragoneater67 talk contribs (mobile) 13:34, 4 September 2026 (UTC)

Syscalls 6 and 7 don't need to read an infinite number of bytes in order for VoidPtr to have an unbounded address space. They only need to support arbitrarily large finite addresses -> Addresses are represented as arbitrarily large finite unsigned integers. Implementations can have practical limits on address size because of resource constraints, but the language specification imposes no fixed upper bound. For example, an address might be represented by 1,2,8,512 ... bytes, Every individual address still has a finite representation and therefore takes a finite amount of time to read. There is no need for an address such as [infinity] to exist. This is the same distinction as an unbounded BF tape: the program can access cell 1,000,000 after finitely many operations without there being an “infinite” cell.

There is no fixed maximum address that the language is restricted to. I'm not proposing that syscall 6 reads infinite bytes. I'm proposing that for every finite address N element of unbounded memory, there is some finite number of bytes sufficient to represent N. The amount isn't bounded globally.

Then youre being restricted to N that the implementation defined, the specification forces the implementation to have a bound, which prevents turing completeness --dragoneater67 talk contribs 14:29, 4 September 2026 (UTC)

I'm not saying that one implementation with a fixed finite N can simulate every possible program. I'm saying that the spec does not impose a single finite bound on N. For every finite amount of address space required by a computation, there is a valid VoidPtr implementation with a sufficiently large N. Basilisk (talk) 14:35, 4 September 2026 (UTC)Basilisk

there cannot exist an implementation that can simulate behaviour of brainfuck +[>+] as it requires N to be infinite, but N must be bounded according to the spec! --dragoneater67 talk contribs 14:46, 4 September 2026 (UTC)

You are right, I have to make 6 and 7 dynamically expandable for it to be TC. Alright, alright, I give up that is a valid argument. Creating infinite VoidPtr machines doesn't make it more TC. I'm not going to add that though because it's stupid considering real hardware. Sorry for wasting your time. Basilisk (talk) 14:56, 4 September 2026 (UTC)Basilisk

i actually have too much free time, so its ok --dragoneater67 talk contribs 15:26, 4 September 2026 (UTC)

you could make it so that you can use an arbitrary number of cells to address memory, for example using $03 $E8 to address cell 1000 ($03E8). then, given a way to increment values which span an arbitrary number of cells, you can recreate that bf program, hence implementing/proving unbounded memory even with a limit on number size --MarkFan8901 (talk) 20:37, 4 September 2026 (UTC)