1441:
1114:
474:
1289:
152:
1221:
1652:
1541:
734:
200:
1059:
972:
language (apart from its I/O commands) is a minor informal variation of P′′. Böhm gives explicit P′′ programs for each of a set of basic functions sufficient to compute any
816:
1579:
1336:
1721:
Böhm, C. and
Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Note: This is the most-cited paper on the
773:
342:
646:
248:
942:
578:
1672:
1599:
1141:
870:
843:
673:
602:
529:
498:
305:
278:
898:
391:
1309:
1185:
1161:
1014:
994:
918:
624:
556:
365:
228:
1780:
1654:, because 8 in base-2 is 100, reverse the digits, and add one to each of them.) At the beginning and end of the computation, the tape-head is on the
1775:
558:
of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
1770:
581:
1361:
1064:
408:
1722:
1709:
Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.
1242:
123:
1190:
1604:
1490:
959:
678:
34:
30:
604:. It is not an instruction and is not used in programs, but is instead used to help define the language.
1601:
before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as
1483:
776:
102:
71:
25:
161:
1311:
times will wrap around so that the result is to "decrement" the symbol in the current cell by one (
1019:
973:
781:
1747:
1546:
1164:
1738:
1314:
741:
310:
963:
631:
233:
41:
927:
563:
106:
46:
1657:
1584:
1119:
848:
821:
651:
587:
507:
483:
477:
283:
256:
110:
1764:
877:
370:
1294:
1170:
1146:
999:
979:
903:
609:
541:
350:
213:
535:
61:
921:
1447:
969:
90:
78:
158:) is formally defined as a set of words on the four-instruction alphabet
1223:. These are the equivalents of the six respective Brainfuck commands ,
1691:
396:
Only words derivable from the previous three rules are words in P′′.
955:
1347:
Böhm gives the following program to compute the predecessor (
703:
1416:
1388:
1323:
1205:
1088:
1034:
139:
136:
130:
626:
means move the tape-head rightward one cell (if possible).
1660:
1607:
1587:
1549:
1493:
1436:{\displaystyle R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr}
1317:
1297:
1245:
1193:
1173:
1149:
1122:
1109:{\textstyle r\equiv \lambda R,r^{\prime }\equiv r^{n}}
1067:
1022:
1002:
982:
930:
906:
880:
851:
824:
784:
744:
681:
654:
634:
612:
590:
566:
544:
510:
486:
411:
373:
353:
313:
286:
259:
236:
216:
164:
126:
1364:
1481:
The program expects an integer to be represented in
84:
70:
60:
52:
40:
24:
1666:
1646:
1593:
1573:
1535:
1435:
1330:
1303:
1283:
1215:
1179:
1155:
1135:
1108:
1053:
1008:
988:
936:
912:
892:
864:
837:
810:
767:
728:
667:
640:
618:
596:
572:
550:
523:
492:
468:
385:
359:
336:
299:
272:
242:
222:
194:
146:
736:, and then move the tape-head leftward one cell.
469:{\textstyle \{\Box ,c_{1},c_{2},\ldots ,c_{n}\}}
16:Primitive programming language created in 1964
8:
1692:"PDBL: A tool for Turing machine simulation"
1446:which translates directly to the equivalent
1284:{\textstyle c_{n+1}\equiv c_{0}\equiv \Box }
463:
412:
189:
165:
147:{\textstyle {\mathcal {P}}^{\prime \prime }}
19:
1717:
1715:
1705:
1703:
1701:
18:
1659:
1635:
1625:
1615:
1606:
1586:
1548:
1527:
1511:
1498:
1492:
1415:
1387:
1363:
1322:
1316:
1296:
1269:
1250:
1244:
1204:
1192:
1172:
1148:
1127:
1121:
1100:
1087:
1066:
1033:
1021:
1001:
981:
929:
905:
879:
856:
850:
829:
823:
802:
789:
783:
759:
749:
743:
706:
702:
686:
680:
659:
653:
633:
611:
589:
565:
543:
515:
509:
485:
457:
438:
425:
410:
372:
352:
328:
318:
312:
291:
285:
264:
258:
235:
215:
163:
135:
129:
128:
125:
101:(P double prime) is a primitive computer
1216:{\textstyle L\equiv r^{\prime }\lambda }
1683:
949:Relation to other programming languages
1647:{\textstyle \Box c_{1}c_{1}c_{2}\Box }
584:saying that the current symbol is not
1536:{\textstyle c_{1},c_{2}\ldots ,c_{k}}
729:{\textstyle c_{(i+1){\bmod {(}}n+1)}}
7:
1781:Experimental programming languages
1291:, incrementing the current symbol
818:. In other words, the instruction
14:
648:means replace the current symbol
109:in 1964 to describe a family of
195:{\textstyle \{R,\lambda ,(,)\}}
1776:Academic programming languages
1746:: Demonstrating the iterative
1424:
1408:
1405:
1399:
1393:
1380:
1374:
1368:
1054:{\textstyle r,r^{\prime },L,R}
1003:
983:
887:
881:
721:
707:
699:
687:
380:
374:
186:
180:
1:
811:{\textstyle q_{2}\circ q_{1}}
1674:preceding the digit-string.
534:All instructions in P′′ are
1797:
1723:structured program theorem
1581:respectively, and to have
1574:{\textstyle 1,2,\ldots ,k}
476:is the tape-alphabet of a
1750:song construed in 337568
480:with left-infinite tape,
89:
77:
1452:
1331:{\textstyle r^{\prime }}
768:{\textstyle q_{1}q_{2}}
367:is a word in P′′, then
337:{\textstyle q_{1}q_{2}}
307:are words in P′′, then
1668:
1648:
1595:
1575:
1537:
1437:
1332:
1305:
1285:
1217:
1181:
1157:
1137:
1110:
1055:
1010:
990:
962:language to be proven
960:structured programming
938:
914:
894:
866:
839:
812:
769:
730:
669:
642:
620:
598:
574:
552:
525:
504:symbol, equivalent to
494:
470:
387:
361:
338:
301:
274:
244:
224:
196:
148:
1771:Models of computation
1669:
1649:
1596:
1576:
1538:
1438:
1333:
1306:
1286:
1218:
1182:
1158:
1138:
1111:
1056:
1011:
991:
939:
924:, with the condition
915:
895:
867:
840:
813:
770:
731:
670:
643:
641:{\textstyle \lambda }
621:
599:
575:
553:
526:
495:
471:
388:
362:
339:
302:
275:
245:
243:{\textstyle \lambda }
225:
197:
154:(hereinafter written
149:
1658:
1605:
1585:
1547:
1543:encoding the digits
1491:
1362:
1315:
1295:
1243:
1191:
1171:
1147:
1120:
1065:
1020:
1000:
980:
937:{\textstyle \alpha }
928:
904:
878:
849:
845:is performed before
822:
782:
777:function composition
742:
679:
652:
632:
610:
588:
573:{\textstyle \alpha }
564:
542:
508:
484:
409:
371:
351:
311:
284:
257:
234:
214:
162:
124:
103:programming language
1694:. 4 September 2021.
1016:and the four words
974:computable function
954:P′′ was the first "
53:First appeared
21:
1748:99 Bottles of Beer
1743:Online interpreter
1667:{\textstyle \Box }
1664:
1644:
1594:{\textstyle \Box }
1591:
1571:
1533:
1433:
1351:-1) of an integer
1328:
1301:
1281:
1239:. Note that since
1213:
1177:
1153:
1136:{\textstyle r^{n}}
1133:
1106:
1051:
1006:
986:
958:-less" imperative
934:
910:
890:
865:{\textstyle q_{2}}
862:
838:{\textstyle q_{1}}
835:
808:
765:
726:
668:{\textstyle c_{i}}
665:
638:
616:
597:{\textstyle \Box }
594:
570:
548:
524:{\textstyle c_{0}}
521:
493:{\textstyle \Box }
490:
466:
383:
357:
334:
300:{\textstyle q_{2}}
297:
273:{\textstyle q_{1}}
270:
240:
220:
192:
144:
393:is a word in P′′.
344:is a word in P′′.
250:are words in P′′.
96:
95:
62:Typing discipline
1788:
1726:
1719:
1710:
1707:
1696:
1695:
1688:
1673:
1671:
1670:
1665:
1653:
1651:
1650:
1645:
1640:
1639:
1630:
1629:
1620:
1619:
1600:
1598:
1597:
1592:
1580:
1578:
1577:
1572:
1542:
1540:
1539:
1534:
1532:
1531:
1516:
1515:
1503:
1502:
1484:bijective base-k
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1442:
1440:
1439:
1434:
1420:
1419:
1392:
1391:
1337:
1335:
1334:
1329:
1327:
1326:
1310:
1308:
1307:
1302:
1290:
1288:
1287:
1282:
1274:
1273:
1261:
1260:
1238:
1234:
1230:
1226:
1222:
1220:
1219:
1214:
1209:
1208:
1186:
1184:
1183:
1178:
1162:
1160:
1159:
1154:
1142:
1140:
1139:
1134:
1132:
1131:
1115:
1113:
1112:
1107:
1105:
1104:
1092:
1091:
1060:
1058:
1057:
1052:
1038:
1037:
1015:
1013:
1012:
1007:
995:
993:
992:
987:
943:
941:
940:
935:
919:
917:
916:
911:
899:
897:
896:
893:{\textstyle (q)}
891:
871:
869:
868:
863:
861:
860:
844:
842:
841:
836:
834:
833:
817:
815:
814:
809:
807:
806:
794:
793:
774:
772:
771:
766:
764:
763:
754:
753:
735:
733:
732:
727:
725:
724:
711:
710:
674:
672:
671:
666:
664:
663:
647:
645:
644:
639:
625:
623:
622:
617:
603:
601:
600:
595:
579:
577:
576:
571:
557:
555:
554:
549:
530:
528:
527:
522:
520:
519:
499:
497:
496:
491:
475:
473:
472:
467:
462:
461:
443:
442:
430:
429:
392:
390:
389:
386:{\textstyle (q)}
384:
366:
364:
363:
358:
343:
341:
340:
335:
333:
332:
323:
322:
306:
304:
303:
298:
296:
295:
279:
277:
276:
271:
269:
268:
249:
247:
246:
241:
229:
227:
226:
221:
201:
199:
198:
193:
153:
151:
150:
145:
143:
142:
134:
133:
42:Designed by
22:
1796:
1795:
1791:
1790:
1789:
1787:
1786:
1785:
1761:
1760:
1758:
1735:
1730:
1729:
1720:
1713:
1708:
1699:
1690:
1689:
1685:
1680:
1656:
1655:
1631:
1621:
1611:
1603:
1602:
1583:
1582:
1545:
1544:
1523:
1507:
1494:
1489:
1488:
1487:notation, with
1479:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1411:
1383:
1360:
1359:
1345:
1343:Example program
1318:
1313:
1312:
1293:
1292:
1265:
1246:
1241:
1240:
1236:
1232:
1228:
1224:
1200:
1189:
1188:
1169:
1168:
1145:
1144:
1123:
1118:
1117:
1096:
1083:
1063:
1062:
1029:
1018:
1017:
998:
997:
978:
977:
964:Turing-complete
951:
926:
925:
902:
901:
876:
875:
852:
847:
846:
825:
820:
819:
798:
785:
780:
779:
755:
745:
740:
739:
682:
677:
676:
655:
650:
649:
630:
629:
608:
607:
586:
585:
562:
561:
540:
539:
511:
506:
505:
482:
481:
453:
434:
421:
407:
406:
403:
369:
368:
349:
348:
324:
314:
309:
308:
287:
282:
281:
260:
255:
254:
232:
231:
212:
211:
208:
160:
159:
127:
122:
121:
119:
111:Turing machines
17:
12:
11:
5:
1794:
1792:
1784:
1783:
1778:
1773:
1763:
1762:
1756:
1755:
1734:
1733:External links
1731:
1728:
1727:
1711:
1697:
1682:
1681:
1679:
1676:
1663:
1643:
1638:
1634:
1628:
1624:
1618:
1614:
1610:
1590:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1530:
1526:
1522:
1519:
1514:
1510:
1506:
1501:
1497:
1453:
1444:
1443:
1432:
1429:
1426:
1423:
1418:
1414:
1410:
1407:
1404:
1401:
1398:
1395:
1390:
1386:
1382:
1379:
1376:
1373:
1370:
1367:
1344:
1341:
1340:
1339:
1325:
1321:
1304:{\textstyle n}
1300:
1280:
1277:
1272:
1268:
1264:
1259:
1256:
1253:
1249:
1212:
1207:
1203:
1199:
1196:
1180:{\textstyle r}
1176:
1156:{\textstyle n}
1152:
1130:
1126:
1103:
1099:
1095:
1090:
1086:
1082:
1079:
1076:
1073:
1070:
1050:
1047:
1044:
1041:
1036:
1032:
1028:
1025:
1009:{\textstyle )}
1005:
989:{\textstyle (}
985:
966:
950:
947:
946:
945:
933:
913:{\textstyle q}
909:
900:means iterate
889:
886:
883:
873:
859:
855:
832:
828:
805:
801:
797:
792:
788:
762:
758:
752:
748:
737:
723:
720:
717:
714:
709:
705:
701:
698:
695:
692:
689:
685:
662:
658:
637:
627:
619:{\textstyle R}
615:
605:
593:
569:
559:
551:{\textstyle X}
547:
532:
518:
514:
489:
478:Turing machine
465:
460:
456:
452:
449:
446:
441:
437:
433:
428:
424:
420:
417:
414:
402:
399:
398:
397:
394:
382:
379:
376:
360:{\textstyle q}
356:
345:
331:
327:
321:
317:
294:
290:
267:
263:
251:
239:
223:{\textstyle R}
219:
207:
204:
202:, as follows:
191:
188:
185:
182:
179:
176:
173:
170:
167:
141:
138:
132:
118:
115:
94:
93:
87:
86:
82:
81:
75:
74:
68:
67:
64:
58:
57:
54:
50:
49:
44:
38:
37:
28:
15:
13:
10:
9:
6:
4:
3:
2:
1793:
1782:
1779:
1777:
1774:
1772:
1769:
1768:
1766:
1759:
1754:instructions.
1753:
1749:
1745:
1744:
1742:
1737:
1736:
1732:
1724:
1718:
1716:
1712:
1706:
1704:
1702:
1698:
1693:
1687:
1684:
1677:
1675:
1661:
1641:
1636:
1632:
1626:
1622:
1616:
1612:
1608:
1588:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1528:
1524:
1520:
1517:
1512:
1508:
1504:
1499:
1495:
1486:
1485:
1451:
1449:
1430:
1427:
1421:
1412:
1402:
1396:
1384:
1377:
1371:
1365:
1358:
1357:
1356:
1354:
1350:
1342:
1319:
1298:
1278:
1275:
1270:
1266:
1262:
1257:
1254:
1251:
1247:
1210:
1201:
1197:
1194:
1174:
1166:
1150:
1143:denoting the
1128:
1124:
1101:
1097:
1093:
1084:
1080:
1077:
1074:
1071:
1068:
1048:
1045:
1042:
1039:
1030:
1026:
1023:
976:, using only
975:
971:
967:
965:
961:
957:
953:
952:
948:
931:
923:
907:
884:
874:
857:
853:
830:
826:
803:
799:
795:
790:
786:
778:
760:
756:
750:
746:
738:
718:
715:
712:
696:
693:
690:
683:
660:
656:
635:
628:
613:
606:
591:
583:
567:
560:
545:
537:
533:
516:
512:
503:
487:
479:
458:
454:
450:
447:
444:
439:
435:
431:
426:
422:
418:
415:
405:
404:
400:
395:
377:
354:
346:
329:
325:
319:
315:
292:
288:
265:
261:
252:
237:
217:
210:
209:
205:
203:
183:
177:
174:
171:
168:
157:
116:
114:
112:
108:
104:
100:
92:
88:
83:
80:
76:
73:
69:
65:
63:
59:
55:
51:
48:
45:
43:
39:
36:
32:
29:
27:
23:
1757:
1751:
1740:
1739:
1686:
1482:
1480:
1445:
1352:
1348:
1346:
536:permutations
501:
155:
120:
107:Corrado Böhm
98:
97:
47:Corrado Böhm
538:of the set
105:created by
1765:Categories
1678:References
922:while loop
775:means the
500:being the
117:Definition
85:Influenced
35:structured
31:Imperative
1662:◻
1642:◻
1609:◻
1589:◻
1563:…
1518:…
1450:program:
1448:Brainfuck
1417:′
1389:′
1324:′
1279:◻
1276:≡
1263:≡
1211:λ
1206:′
1198:≡
1094:≡
1089:′
1075:λ
1072:≡
1035:′
970:Brainfuck
932:α
796:∘
636:λ
592:◻
582:predicate
568:α
488:◻
448:…
416:◻
401:Semantics
238:λ
175:λ
140:′
137:′
91:Brainfuck
79:Brainfuck
1355:> 0:
72:Dialects
26:Paradigm
1165:iterate
66:untyped
1187:, and
1061:where
206:Syntax
1116:with
920:in a
675:with
580:is a
502:blank
1473:>
1467:<
1458:<
1455:>
1237:>
1233:<
968:The
956:GOTO
280:and
230:and
56:1964
1752:P′′
1741:P′′
1167:of
1163:th
704:mod
347:If
253:If
156:P′′
99:P′′
20:P′′
1767::
1725:.)
1714:^
1700:^
1338:).
1235:,
1231:,
1227:,
996:,
113:.
33:,
1637:2
1633:c
1627:1
1623:c
1617:1
1613:c
1569:k
1566:,
1560:,
1557:2
1554:,
1551:1
1529:k
1525:c
1521:,
1513:2
1509:c
1505:,
1500:1
1496:c
1476:+
1470:]
1464:−
1461:]
1431:r
1428:R
1425:)
1422:L
1413:r
1409:)
1406:)
1403:L
1400:(
1397:L
1394:(
1385:r
1381:(
1378:L
1375:)
1372:R
1369:(
1366:R
1353:x
1349:x
1320:r
1299:n
1271:0
1267:c
1258:1
1255:+
1252:n
1248:c
1229:-
1225:+
1202:r
1195:L
1175:r
1151:n
1129:n
1125:r
1102:n
1098:r
1085:r
1081:,
1078:R
1069:r
1049:R
1046:,
1043:L
1040:,
1031:r
1027:,
1024:r
1004:)
984:(
944:.
908:q
888:)
885:q
882:(
872:.
858:2
854:q
831:1
827:q
804:1
800:q
791:2
787:q
761:2
757:q
751:1
747:q
722:)
719:1
716:+
713:n
708:(
700:)
697:1
694:+
691:i
688:(
684:c
661:i
657:c
614:R
546:X
531:.
517:0
513:c
464:}
459:n
455:c
451:,
445:,
440:2
436:c
432:,
427:1
423:c
419:,
413:{
381:)
378:q
375:(
355:q
330:2
326:q
320:1
316:q
293:2
289:q
266:1
262:q
218:R
190:}
187:)
184:,
181:(
178:,
172:,
169:R
166:{
131:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.