2024-12-11 15:10:53 C is turing complete 2024-12-11 15:15:25 that's news to me! 2024-12-11 16:08:24 Now, is turing C complete? 2024-12-11 16:21:40 Turing completeness is not necessarily something you want 2024-12-11 16:21:50 ook! 2024-12-11 16:22:26 C is probably not what you want 2024-12-11 16:22:28 (which is also an turing tarpit btw) 2024-12-11 16:23:06 https://en.wikipedia.org/wiki/Total_functional_programming 2024-12-11 16:24:49 one thing I mulled on is pra, which stands for primitive recursive algorytthms 2024-12-11 16:25:37 why? well I was thinking of an extension to the Remote Frame Buffer protocol 2024-12-11 16:27:02 as pra programs are guranteed to terminate I thought they were/are safe enough for doing frame buffer manipulation 2024-12-11 16:28:28 basically this would be extra encoding option to deal with pixel data 2024-12-11 16:29:59 the only two control flow primitive allowed would be down counting loops and if else then constructs 2024-12-11 16:31:35 the rest would be built by macros that have basically 'holes' (args to the macro) that get filled at 'use' time 2024-12-11 16:32:10 a macro can only refer to previous defined macros so no recursion 2024-12-11 16:34:41 the instructions would be running in a dual stack envirion (pretty much like Bitcoin Script) and encoded as wholenums. (unsigned ints where the upper most bit of each byte is basically "not done" boolean) 2024-12-11 16:35:46 cell size would be at least 32 bit 2024-12-11 16:37:41 this would pretty much enable sending imagery as 'draw this kind of rect I specified earlier' instructions 2024-12-11 16:55:53 GeDaMo: I agree, it's a theoretical definition which is overused in programming language discussion 2024-12-11 16:56:29 However I was under impression, and have seen it stated, that C is not turing complete. And I don't think that's actually true, I think it is turing complete. 2024-12-11 16:56:50 For whatever that means 2024-12-11 17:24:51 i thought the "c is not turing complete" camp comes from the fact that pointer size is finite, but that seems like a weak argument since you could surely think up some kind of arbitrary precision addressing scheme 2024-12-11 17:26:24 although then i guess your arbitrary precision addresses would still be limited to a finite address range. maybe they're on to something, i don't know. i'm not sure i ever really understood turing completeness or why i should care. 2024-12-11 17:27:15 I think that camp's argument is wrong because they've imposed an arbitrary limitation on C here, that there must be some way to build the program to run any input 2024-12-11 17:27:44 But I think the definition of turing completeness permits us to rebuild to a machine based on the input size 2024-12-11 17:28:08 So if you have input that needs a bigger 'tape' then you can theoretically use a larger architecture 2024-12-11 17:28:47 The fact that you can't practically use any architecture is like the fact you can't practically have unbounded memory, it's irrelevant to the question of turing completeness 2024-12-11 17:29:04 So I can just say "okay let's say I have a 1024-bit address machine" 2024-12-11 17:29:12 Or "N-bit address machine" 2024-12-11 17:29:52 I can fix N after receiving the input, the same way I can fix the size of my physical computer's RAM after receiving input 2024-12-11 17:30:57 C is actually turing complete because you can have streams be seekable and unbounded at the same time, theoretically 2024-12-11 17:30:57 the same way nobody actually makes an infinite tape for a turing machine, it's only in theory 2024-12-11 17:31:07 But this is moot because the whole fixed address size thing wasn't an issue in the first place 2024-12-11 17:31:57 Also if that was the only argument then you'd have people saying "freestanding C isn't turing complete" instead 2024-12-11 17:32:33 And this same logic applies to Forth too, I would say 2024-12-11 18:23:24 I agree with that - I'd say it applies to any real system, since they all have bounded state spaces. 2024-12-11 19:01:49 it's a very abstract, theoretical thing, of course. for example, one could argue that lua doesn't have this limitation because it doesn't have numeric pointers, it only has objects. how those objects are addressed is abstracted away entirely. the language of c mandates that you can write sizeof (void *), so a void * must have a finite size. 2024-12-11 20:00:09 Basically you can always choose to run it on a computer with more RAM, so therefore you can always choose to compile + run it on a computer with more address bits 2024-12-11 20:00:15 That's my logic 2024-12-11 20:01:15 Whether it really applies is probably down to some very specific rules on how you define 'turing complete' in context of a programming language, and that is less about universal turing machines, and more subjective 2024-12-11 20:01:19 yeah, and i buy that, too. like i said, i don't think i ever really "got" the whole turing complete thing. 2024-12-11 20:01:43 It's nonsense for actual programming 2024-12-11 20:02:03 Turing had a lot fewer computers to work with 2024-12-11 20:02:18 But I have to push back because people with cheetos wedged in their teeth are sneering 2024-12-11 20:02:38 You know the sort! :P 2024-12-11 20:04:30 yes i aspire to be one some day 2024-12-11 20:10:54 if you define language turing-completeness as "can simulate other programming languages (which supposedly can emulate turing machines)", then C can do that if you hate yourself, if you define it as "unprovable termination" then you should do better than that, if you define it as "shares all important properties with turing machines and can simulate one" then C is turing complete as long as you have a way to do IO 2024-12-11 20:11:57 while C is technically a finite state machine, the moment you can do unbounded IO (as previously stated, you can in C), you have a turing machine 2024-12-11 20:14:49 or rather, C's abstract machine is a finite state machine 2024-12-11 20:42:03 identity I think you've missed the wood for the trees here 2024-12-11 20:43:11 C constrained to one implementation is a finite state machine without the IO, but why would I make that constraint? 2024-12-11 20:43:41 It's a bit like saying Lua is finite if I limit the RAM ... er yeah 2024-12-11 20:45:10 The only question is whether you can define an environment to execute a given input, the C program (i.e. the source) doesn't need to change for this 2024-12-11 20:45:42 idk, i've seen a lot of c programs where the source needs to change 2024-12-11 20:46:52 I can write a portable one though 2024-12-11 20:47:10 yeah, i'm just saying people don't :) 2024-12-11 20:47:18 Not usually worth supporting n-bit arch though 2024-12-11 20:47:36 But that's besides the point 2024-12-11 20:48:03 of course. the point is that c is a great programming language and we all love it, and there is no disputing this fact. 2024-12-11 20:48:12 :P 2024-12-11 20:48:23 i'm not sure what you mean by "constrained to one implementation" 2024-12-11 20:52:05 My point is that you are doing this by saying C is a finite state machine: it is when you choose an implementation, but if you don't then theoretically it's unbounded 2024-12-11 20:53:33 C's abstract machine is a finite state machine, i don't see how a different implementation would change it without violating the rules of C's abstract machine 2024-12-11 20:53:50 could you explain? 2024-12-11 20:53:51 Not one different, but an undecided implementation 2024-12-11 21:02:41 nothing that can ever physically exist is turing complete 2024-12-11 21:02:49 because turing machines can be infinitely large 2024-12-11 21:05:36 well theoretically they are a theoretical model of theoretical computation for theorising 2024-12-11 22:28:07 veltas: I think "Turing complete" PRESUMES an underlying system with infinite resources. The whole idea isn't really targeted at the SCALE of the machine, but rather comments on its set of atomic actions (its instructions). It's the instruction set that's either Turing complete or not.\ 2024-12-11 22:29:29 It's like "universal" sets of logic gates. NAND is universal all on its own, because you can implement any binary function using only NAND. But obviously you just assume you have enough of them to do the job. 2024-12-11 22:41:14 I didn't specifically mean that reading existing illuminated medieval manuscripts is a major use case for me (I have a lot of trouble with all the scribal abbreviations, even when I can handle the Latin) but rather that there is no reason for my computer user interface to look uglier than a medieval illuminated manuscript. I mean, it's no longer necessary to import lapis lazuli and grind it up by hand to 2024-12-11 22:41:20 color letters blue. 2024-12-11 22:44:31 alas, I accidentally compiled color support out of st 2024-12-11 22:47:09 just get a marker pen 2024-12-11 23:03:12 Thas really careless thrig 2024-12-11 23:04:21 I accidentally used xterm and xfce4-terminal instead of st everywhere 2024-12-11 23:06:25 xterm is also configured to nuke colors 2024-12-11 23:33:39 Not a CEEFAX fan? 2024-12-11 23:34:24 1+ for teletext 2024-12-11 23:39:12 When I see gaudy colours in a terminal it always reminds me of teletext 2024-12-11 23:46:06 ever use any videotex services? 2024-12-11 23:46:32 i guess prestel would've been a british one 2024-12-11 23:46:56 No never, every TV when I was young had teletext though 2024-12-11 23:48:49 Apparently it was only big in France 2024-12-11 23:52:01 Well I used dial-up! 2024-12-11 23:52:06 In terms of "doing the most with the least", I think monospace fonts are an anachronistic accommodation to the limitations of mechanical typewriters and discrete-chip circuitry. Non-monospace pixel fonts are often not even more code to support, and they certainly allow you to do more with less pixels 2024-12-11 23:52:27 When you're right you're right 2024-12-11 23:53:58 Did you see Gordon Letwin's post on OS/2? https://gunkies.org/wiki/Gordon_Letwin_OS/2_usenet_post 2024-12-11 23:54:33 There's an interesting bit in there about TopView which reminds me of this