01:55:40 <esowiki> [[User:B jonas]] https://esolangs.org/w/index.php?diff=53638&oldid=53333 * B jonas * (+26)

12:06:38 <esowiki> [[User:B jonas]] https://esolangs.org/w/index.php?diff=53639&oldid=53638 * B jonas * (+30)

13:02:23 <mroman> `if H(P) then endless_loop(); else halt();` usually assumes that H is an external "machine/program" you invoke

13:02:24 <HackEgo> bash: -c: line 0: syntax error near unexpected token `P' \ bash: -c: line 0: `if H(P) then endless_loop(); else halt();` usually assumes that H is an external "machine/program" you invoke'

13:03:20 <esowiki> [[Gb gates RISC]] N https://esolangs.org/w/index.php?oldid=53640 * B jonas * (+4593) Created page with "{{DISPLAYTITLE: Gb_gates RISC}} '''Gb_gates RISC''' is a very small hypothetical microprocessor created by Donald Knuth. He has created a software implementation of this micr..."

13:04:32 <esowiki> [[Gb gates RISC]] https://esolangs.org/w/index.php?diff=53641&oldid=53640 * B jonas * (+90)

13:05:12 <esowiki> [[Language list]] https://esolangs.org/w/index.php?diff=53642&oldid=53628 * B jonas * (+20)

13:05:21 <int-e> mroman: H should be inlined. And in any case the proofs rely on interpreters, because you cannot pass programs around, only descriptions of programs.

13:06:02 <HackEgo> 2 tablespoon of the whipped cream into the pan in lightly floured \ get and deep flour and including for 1 hour. Top with side of \ the sugar, chopped fresh chop more. \ \ Recipe By : Low-Bobbie Cooking \ \ MMMMM \ \ MMMMM----- Recipe via Meal-Master (tm) v8.05 \ \ Title: ICE ENCION COOKIES \ Categories: Desserts, Germanaus \ Yield: 4

13:07:59 <int-e> mroman: So what you really do is write a program P'(h,p) = if H(eval(p(h,p))) then endless_loop else halt; And then look at P'([H],[P']), where [_] is the description of the program inside the brackets.

13:08:23 <int-e> and eval is the interpreter, and the p(h,p) inside there is actually a kind of substitution.

13:09:40 <int-e> P' knows what H is. P' doesn't know what P is, but it will be told what P' is and can then reconstruct P from P' and H.

13:13:29 <int-e> (the p(p) inside is still cheating with notation, it's an operation that takes p to be a description of a program P(x) with a single parameter, and replaces x by a description of the value p, syntactically.)

13:14:50 <int-e> ... which will end up being P'([P']), I'm afraid I'm not explaining this very well.

13:15:24 <mroman> I assume that there's a program H that can determine whether P halts or not but P doesn't know H.

13:16:06 <int-e> But anyway, in "if H(P) then loop else halt", H is never the problem. It's the reference of P to itself which you need to escape.

13:17:07 <int-e> mroman: btw this isn't anything unusual. The trick here is essentially the same as that for writing quines.

13:17:37 <int-e> Rather than having P store its full source code, it stores about half of it, and reconstructs the full source code from that.

13:19:45 <int-e> You assume that H exists, then you make a program that H cannot decide the halting problem for.

13:23:06 <mroman> I can't make arguments based on the assumption that P can include H and then call H

13:23:22 <int-e> But you /can/ make a description of H a parameter of P, which I mostly did when I wrote (almost) "P'(h,p) = if eval(h(p(h,p))) then loop else halt" By partial substitution you can make P(h) = if eval(h(P'(h,[P'])) then halt alse loop", so that's a program for which, H cannot decide termination of P([H]).

13:24:59 <mroman> so I could fit an infinitely large program in there and then my turing machine interprets that program

13:29:52 <mroman> the proof is essentially that for a turing machine T(x) = y an input i exists such that T(i) = i

13:34:16 <int-e> The program doesn't contain itself, just a description of something that behaves like itself.

13:37:33 <mroman> Assume a halting program H exists that can answer whether P halts or not (P being a SPECIFIC program).

13:37:59 <mroman> For the argument `P = if H(P) then loop() else halt` to work P needs to contain itself and it needs to contain its halting program (in whatever form)

13:38:01 <int-e> (the "> text$ap(++)show" isn't even the program itself; it's missing a constant. the ap(++)show does the substitution (degenerated; it appends the string to the partial program); that is the description of the program itself. And for the halting problem, you'd pass something like that to H.)

13:40:02 <int-e> For any specific program P, one of the two TMs that always reject or always accept will decide the halting problem for P.

13:40:56 <mroman> I'm trying to understand if for every P an H exists that answers whether P halts or not

13:41:25 <int-e> The halting problem is the problem of finding a program H such that for any program P, H accepts [P] if and only if P halts.

13:42:44 <int-e> mroman: I just answered that question. Yes, but not in any interesting way, because unless we already know whether P terminates of not, we don't know which of the two candidates for H is the right one.

13:44:19 <int-e> However, I was under the impression that we were discussing the halting problem. Now that I've figured out that we're not doing that I'm no longer interested.

13:44:47 <esowiki> [[User:B jonas]] https://esolangs.org/w/index.php?diff=53643&oldid=53639 * B jonas * (-26)

13:45:27 <mroman> I accept the proof for the halting problem based on the assumption that P can communicate with H over some form of I/O.

13:46:42 <int-e> Well you're wrong. And I think you have a wrong statement of the halting problem in mind. I don't know what that statement is.

13:48:19 <mroman> if P can't communicate with H it could only do that if P contains a copy of H but if P contains a copy of H it inherently needs to know what H actually is.

13:49:41 <int-e> (Actually it's not, it's negation introduction, so even intuitionistically you should not have any complaints.)

13:50:25 <int-e> Suppose H exists. Then there would be a program P such that H gets termination of P wrong. Hence H doesn't exist.

13:51:39 <mroman> Essentially I'm saying the program you construct to proof the non-existence can itself not exist.

13:52:22 <int-e> All the programs "P" in that proof are necessarily hypothetical, though they can be obtained by making a description of H a parameter of P. But whatever you ultimately pass to H in order to obtain a contradiction will contain H or a description of H.

13:52:51 <mroman> for the P that was given to you you write a program that answers whether P halts or not (without prior knowledge about whether P halts or not)

13:52:52 <int-e> mroman: If you fix P you're discussing something entirely different from the halting problem.

13:54:04 <esowiki> [[BuzzFizz]] https://esolangs.org/w/index.php?diff=53644&oldid=53634 * B jonas * (+1) /* External resources */

13:56:22 <int-e> APic: or just start feeding parameters and strings of increasing length to $program

13:56:58 <int-e> (you'll need some lenience because of kerning and the like, but it seems to me that this stupid approach should be good enough anyway)

14:04:44 <int-e> mroman: it doesn't. Q is entirely hypothetical, based on the assumption that H exists.

14:06:10 <int-e> mroman: This is like the largest prime. If 2 = p_1 < p_2 < ... < p_n is a complete list of primes, then p_1*...*p_n+1 is not divisible by any (other) prime, hence must be prime as well, a contradiction. So there is no such complete list of primes.

14:06:47 <int-e> And then it turns out that in most cases, p_1*...*p_n+1 for a prefix of the list of primes is not actually prime but divisible by some other prime...

14:08:55 <int-e> despite the fact that under the hypothesis that 2,3,5,7,11,13 contains all primes, it would be prime. Ex falso quod libet.

14:12:01 <int-e> mroman: and for part 1), the trouble is that by the law of excluded middle, P either terminates (and then H exists), or P doesn't terminate (and H exists). So classically, H exists. Constructively, you're back in halting problem territory, because without further information on P, you need a /uniform/ construction for H that works for all possible P.

14:13:59 <int-e> (Such a construction can be performed by a Turing Machine, and the result can be evaluated using a universal TM (vulgo interpreter))

14:15:08 <int-e> I'll readily admit that this is all rather subtle and full of pitfalls. I can't even promise that I'm avoiding all of them successfully, but I'm trying. :)

14:32:19 <HackEgo> nuntcoin blintercoin obstocoin coborcoin micrcoin lndcoin crabicoin sholdcoin eldcoin brycoin mirecoin redchcoin trainccoin omercoin codecoin mdccoin djousioncoin q-balcoin surfcoin osseacoin

14:37:52 <variable> [05:54:40] <APic>One could hack some OCR-Software to convert Letters back to Pixels

14:39:27 <int-e> variable: maybe I shouldn't laugh. undoing this kind of OCR could be quite tricky: http://int-e.eu/~bf3/tmp/ocr.png

14:39:30 <variable> int-e: what happens if I take your derivative. Do you become 'e'? or int-int-e? or something else ?

14:42:16 <HackEgo> #esoteric bitmap fonts include: \oren\'s font http://www.orenwatson.be/fontdemo.htm , lifthrasiir's font https://github.com/lifthrasiir/unison/ https://lifthrasiir.github.io/unison/sample.png , b_jonas's font http://www.math.bme.hu/~ambrus/pu/fecupboard20-c.pcf.gz , fizzie's font https://github.com/fis/rfk86/tree/master/web/font

16:57:42 <zzo38> Would it possible to improve the OCR by cropping pictures of each individual letter and then specifying what letters they are, and see if that improve them?

17:01:10 <zzo38> To avoid having to retype the entire document, so that you only have to retype a part of it.

23:45:52 <oerjan> int-e: well i don't think your explanation was precise enough to get past the horrible miscommunication barrier at a reasonable speed.

23:48:25 <oerjan> i suppose this may have some of the same flavor as those arguments people have over cantor's theorem for real numbers...