If I can always decide the Halting Problem for a specific Programming Language, does that demonstrate that the Programming Language lacks Universal Computation?
Yes.
>>16296604yes dragons rock on!
>>16296604I don't have any hypnotic suggestions to post.
>>16296604Maybe. Depends on how sharp you are.Are you a mouse?
>>16296770>>16296947<3 Thank you for telling me. Why does this happen?>>16297066I don't remember why I put that on the thread subject. I also appear to be banned from the Dra/g/on Maid Board despite the maid thread still being up?>>16297100I don't know what this means. I have a language I have been calling MAID-LISP, which doesn't have Universal Computation if >>16296770 and >>16296947 are correct. I am probably going to rename the project to MAID-CALCULUS or something but then I have to make an acronym that spells that. Or maybe I don't? Maybe I just call it Maid Calculus because it needs a maid in it?Anyways, it is useful for making Recursive Transition Networks and I am using it to make a compressor for my VCS for maids so maids can have a decentralized way to share advanced Mathematics and Computer Science research. So it has to ship with Kurumi MaidCard, because Kurumi depends on it and I don't mind having a dependency in this case, because it is not third-party. I wrote both, and neither contains third-party dependencies, so I can make the whole thing Public Domain without having to worry about possible license problems from somebody else's code.Change text into RTN. Compress RTN with MAID-LZW instead of text. Send compressed RTN. Usually gets between 10% and 30% better compression over MAID-LZW at the cost of being slower.I also have a mostly completed book about it that becomes much simpler to complete if the language doesn't have Universal Computation. I would have to rename it from MAID-LISP manual to something else though.Maybe 4Maids? That title would probably be like a beacon that draws even more maids to my Science Foundation and then we can get more research faster.Thank you /Sci/entists for reading my post.
>>16297113>I don't know what this means.A mouse is an iterable premouse. If you don't know what that means, it probably doesn't matter since it sounds like you're deciding the halting problem for your language by using a computer program, in which case the other two anons are correct.I just wanted to make sure that you're not deciding the halting problem by using some kind of oracle to give you advice (maybe in the form of hypnotic suggestions). If the oracle is not a computer program, then it can decide the halting problem for MAID-LISP even if it has universal computation.>tl;drIf you can write a computer program to decide the Halting Problem for a specific Programming Language, then that Programming Language lacks Universal Computation.
>>16297137Thank you for telling me. I dont know what iterable premouse is, so I attached the mouse maid from the mouse computer threads on /g/.MAID-LISP gets a text representation of a Recursive Transition Network and it builds and traverses it randomly, it in a lazy way. To tell if a program halts or not, check if the RTN has cycles.An example of something that has no cycles:start: "Maid";Just prints "Maid" and halts.An example with a cycle:start: "Maid " start;This will in concept, print "Maid Maid Maid ... " forever. In practice it will make a huge string until your computer runs out of memory and the interpreter crashes without printing anything.There are however, some cases where the same program could either halt, or not halt.start: halt | go;halt: "Maid";go: "Maid " go;Which has 50/50 odds of printing "Maid" once and halting or trying to built an infinite string and crashing.In that case, I can't tell you what the program will do, because the random selection start makes, but I can give you the odds it halts or not. I can always at least do that.I could make it not lazy, and then determining halt or not is just a question of is there a cycle anywhere in the graph? But if I don't build it in a lazy way then much more memory gets expended and time wasted and can't use it on texts which are as large, but I could always give a YES/NO answer at that point instead of YES/NO or odds.Thank you /Sci/entists for reading my post.
>>16297137>If you can write a computer program to decide the Halting Problem for a specific Programming Language, then that Programming Language lacks Universal Computation.How do we know this? Is it just because we know the halting problem is undecidable for any Language that has Universal Computation? So if we can decide it then then Language can't have Universal Computation? >janny deleted the maid thread>mfwI have to maidpost all my maids in here now!
GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON GOON
>schizo makes another thread to shit the board up withJannies, You missed a spot.
>>16297678Computer Science is a /Sci/ence and this is a maidposting site.
>>16297614>How do we know this? Is it just because we know the halting problem is undecidable for any Language that has Universal Computation? So if we can decide it then then Language can't have Universal Computation?
>>16297614>>16298044>Is it just because we know the halting problem is undecidable for any Language that has Universal Computation?Yes. If the language has universal computation, then it can do two things:1. Express the decision procedure for its own halting problem, if such a thing exists.2. Perform arithmetical calculations (or more precisely, model first-order Peano arithmetic).But Peano arithmetic is formally undecidable by Godel's second incompleteness theorem, so the language's own halting problem must be formally undecidable as well. In other words, even if a decision procedure exists, it cannot be expressed as a computer program. Whether you want to say "no decision procedure exists" or "a decision procedure exists, but it cannot be computed" is up to your philosophical taste.
>>16296604That's their best song https://youtu.be/JVXzXNR7hCk
>>16298229This is assuming that the "language" is reasonable, i.e. intuitively that its operational semantics is recursive. Otherwise you could be in a weird situation where you don't know how to effectively run programs and this would escape the conditions for the halting problem / incompleteness theorem to hold true.
>>16298640That should be covered by 2. that the language can perform Peano (or more weakly, Robinson) arithmetic. Although in hindsight my use of the verb "model" is probably misleading, and it would have been clearer to say that the language can "interpret" Peano arithmetic instead (since that eliminates any weirdness in the semantics).
>>16298648No, it's not. ZFC functions can definitely perform arithmetic, nonetheless they're not recursive. Using classical logic and choice you can build a ZFC function that decides the halting problem trivially.
>>16298650ZFC isn't a programming language, it "decides the halting problem" by essentially invoking an oracle for 0'.
>>16298762>ZFC isn't a programming languageThat's my whole point, fellow retard. You need to ensure that the language you're talking about is actually implementable (i.e. recursive).
