414:
25:
89:
using only the symbols 0 and 1. Using the S and K combinators, complex boolean algebra functions can be made. BCL has applications in the theory of program-size complexity (
583:
340:
Thus there are four equivalent formulations of BCL, depending on the manner of encoding the triplet (K, S, left parenthesis). These are
689:
629:
501:
61:
43:
662:
694:
575:
315:
479:
266:
360:
90:
219:
534:
82:
484:
434:
672:
430:
625:
497:
330:
115:
86:
617:
542:
489:
418:
337:
corresponds to a left parenthesis, right parentheses being unnecessary for disambiguation.)
556:
511:
552:
507:
364:
538:
426:
683:
609:
446:
402:
are arbitrary subterms. (Note, for example, that because parsing is from the left,
413:
621:
493:
650:
368:
667:
372:
118:, logical functions can be represented in as functions of combinators:
547:
645:
470:
469:
Tromp, John (2007), "Binary lambda calculus and combinatory logic",
85:
that uses binary terms 0 and 1 to create a complete formulation of
34:
provides insufficient context for those unfamiliar with the subject
417:
One step of Rule 110 Cellular
Automata in SK-Basis(Written in the
18:
655:
525:
Devine, Sean (2009), "The insights of algorithmic entropy",
363:
of BCL, apart from eta-reduction (which is not required for
646:
John's Lambda
Calculus and Combinatory Logic Playground
39:
478:, World Sci. Publ., Hackensack, NJ, pp. 237–260,
367:), may be very compactly specified by the following
614:Randomness and Complexity, from Leibniz to Chaitin
122:List of Logical Operations as Binary Combinators
610:"Binary Lambda Calculus and Combinatory Logic"
425:BCL can be used to replicate algorithms like
8:
546:
483:
62:Learn how and when to remove this message
412:
120:
464:
462:
458:
385:11101xyz → 11xz1yz
44:providing more context for the reader
7:
569:
567:
565:
380: 1100xy → x
371:rules for subterms of a given term,
269:of BCL may be specified as follows:
663:"Lambda Diagrams YouTube Playlist"
14:
675:from the original on 2021-12-21.
576:"Combinators: A Centennial View"
23:
586:from the original on 2020-12-06
574:Wolfram, Stephen (2021-12-06).
690:Algorithmic information theory
298:" abbreviates "the meaning of
1:
651:A minimal implementation in C
344:(as in the present version),
16:Computer programming language
656:Lambda Calculus in 383 Bytes
608:Tromp, John (October 2007).
580:writings.stephenwolfram.com
711:
622:10.1142/9789812770837_0014
494:10.1142/9789812770837_0014
198:S(S(S(SS(K(K(KK)))))(KS))
472:Randomness and complexity
126:
224:
208:S(S(S(SS)(S(S(SK)))S))K
188:S(S(K(S(SS(K(KK)))))))S
75:Binary combinatory logic
422:
267:denotational semantics
416:
361:operational semantics
354:(11, 10, 0)
350:(10, 11, 0)
346:(01, 00, 1)
342:(00, 01, 1)
168:SS(S(S(S(SK))S))(KK)
91:Kolmogorov complexity
406:is not a subterm of
83:programming language
539:2009Entrp..11...85D
365:Turing completeness
123:
114:combinators of the
40:improve the article
423:
319:-basis combinators
121:
695:Combinatory logic
631:978-981-277-082-0
548:10.3390/e11010085
503:978-981-277-082-0
431:Cellular automata
331:combinatory logic
212:
211:
116:Combinatory logic
87:combinatory logic
72:
71:
64:
702:
676:
635:
595:
594:
592:
591:
571:
560:
559:
550:
522:
516:
514:
487:
477:
466:
419:Wolfram Language
409:
405:
401:
397:
393:
386:
381:
355:
351:
347:
343:
336:
324:
313:
307:
301:
297:
291:
286:
278:
256:
253:
250:
247:
244:
241:
237:
234:
231:
228:
220:Backus–Naur form
129:Boolean Algebra
124:
81:) is a computer
67:
60:
56:
53:
47:
27:
26:
19:
710:
709:
705:
704:
703:
701:
700:
699:
680:
679:
661:Brauner, Paul.
660:
642:
632:
607:
604:
602:Further reading
599:
598:
589:
587:
573:
572:
563:
524:
523:
519:
504:
485:10.1.1.695.3142
475:
468:
467:
460:
455:
443:
435:Turing complete
427:Turing machines
407:
403:
399:
395:
391:
384:
379:
375:from the left:
353:
349:
345:
341:
334:
333:. (The prefix
322:
309:
303:
299:
296:
289:
281:
273:
263:
258:
257:
254:
251:
248:
245:
242:
239:
235:
232:
229:
226:
217:
104:
99:
68:
57:
51:
48:
37:
28:
24:
17:
12:
11:
5:
708:
706:
698:
697:
692:
682:
681:
678:
677:
658:
653:
648:
641:
640:External links
638:
637:
636:
630:
603:
600:
597:
596:
561:
517:
502:
457:
456:
454:
451:
450:
449:
442:
439:
388:
387:
382:
329:operation, of
293:
292:
287:
279:
262:
259:
225:
216:
213:
210:
209:
206:
203:
200:
199:
196:
193:
190:
189:
186:
183:
180:
179:
176:
173:
170:
169:
166:
162:
161:
158:
154:
153:
148:
144:
143:
138:
134:
133:
130:
127:
103:
100:
98:
95:
70:
69:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
707:
696:
693:
691:
688:
687:
685:
674:
670:
669:
664:
659:
657:
654:
652:
649:
647:
644:
643:
639:
633:
627:
623:
619:
615:
611:
606:
605:
601:
585:
581:
577:
570:
568:
566:
562:
558:
554:
549:
544:
540:
536:
533:(1): 85–110,
532:
528:
521:
518:
513:
509:
505:
499:
495:
491:
486:
481:
474:
473:
465:
463:
459:
452:
448:
445:
444:
440:
438:
436:
432:
428:
420:
415:
411:
383:
378:
377:
376:
374:
370:
366:
362:
357:
338:
332:
328:
320:
318:
312:
306:
288:
285:
280:
277:
272:
271:
270:
268:
260:
223:
221:
214:
207:
204:
202:
201:
197:
194:
192:
191:
187:
184:
182:
181:
177:
174:
172:
171:
167:
164:
163:
159:
156:
155:
152:
149:
146:
145:
142:
139:
136:
135:
131:
128:
125:
119:
117:
113:
109:
101:
96:
94:
92:
88:
84:
80:
76:
66:
63:
55:
45:
41:
35:
32:This article
30:
21:
20:
666:
613:
588:. Retrieved
579:
530:
526:
520:
471:
447:Iota and Jot
424:
389:
358:
339:
326:
316:
310:
304:
294:
283:
275:
264:
238:00 | 01 | 1
218:
150:
140:
111:
107:
105:
78:
74:
73:
58:
49:
38:Please help
33:
616:: 237–260.
327:application
178:S(SS)S(SK)
684:Categories
590:2021-02-17
453:References
132:S-K Basis
106:Utilizing
97:Definition
480:CiteSeerX
433:, BCL is
369:rewriting
302:". Here
290:== ( )
261:Semantics
147:False(0)
102:S-K Basis
52:July 2020
673:Archived
584:Archived
441:See also
408:11010000
314:are the
151:K(K(SK))
137:True(1)
668:YouTube
557:2534819
535:Bibcode
527:Entropy
512:2427553
373:parsing
325:is the
295:where "
628:
555:
510:
500:
482:
398:, and
390:where
352:, and
321:, and
215:Syntax
476:(PDF)
404:10000
185:NAND
141:K(KK)
626:ISBN
498:ISBN
429:and
359:The
308:and
265:The
255:>
252:term
249:<
246:>
243:term
240:<
233:>
230:term
227:<
205:XOR
195:NOR
165:NOT
160:SSK
157:AND
110:and
618:doi
543:doi
490:doi
437:.
410:.)
323:( )
300:...
282:==
274:==
236:::=
175:OR
93:).
79:BCL
42:by
686::
671:.
665:.
624:.
612:.
582:.
578:.
564:^
553:MR
551:,
541:,
531:11
529:,
508:MR
506:,
496:,
488:,
461:^
421:).
394:,
356:.
348:,
317:KS
222::
634:.
620::
593:.
545::
537::
515:.
492::
400:z
396:y
392:x
335:1
311:S
305:K
284:S
276:K
112:S
108:K
77:(
65:)
59:(
54:)
50:(
46:.
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
