Created
July 7, 2025 17:59
-
-
Save SagePtr/67d99bef609ad44925ccb1fbeacf81aa to your computer and use it in GitHub Desktop.
Turing Complete finding optimal 3-bit decoder
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const { Combination } = require("js-combinatorics"); | |
| const and = (a,b) => a & b; | |
| const nor = (a,b) => !(a | b); | |
| const or = (a,b) => (a | b); | |
| const nand = (a,b) => !(a & b); | |
| const b2i = (a) => a ? 1 : 0; | |
| const ops = [ | |
| {'name': 'and', 'fn': and}, | |
| {'name': 'nor', 'fn': nor}, | |
| ]; | |
| const simple_fns = [ | |
| {'name': 'a', 'fn': (a,b,c) => a }, | |
| {'name': 'b', 'fn': (a,b,c) => b }, | |
| {'name': 'c', 'fn': (a,b,c) => c }, | |
| ]; | |
| const advanced_fns = [ | |
| {'name': '!a', 'fn': (a,b,c) => !a }, | |
| {'name': '!b', 'fn': (a,b,c) => !b }, | |
| {'name': '!c', 'fn': (a,b,c) => !c }, | |
| {'name': '(a and b)', 'fn': (a,b,c) => and(a,b) }, | |
| {'name': '(a and c)', 'fn': (a,b,c) => and(a,c) }, | |
| {'name': '(b and c)', 'fn': (a,b,c) => and(b,c) }, | |
| {'name': '(a nor b)', 'fn': (a,b,c) => nor(a,b) }, | |
| {'name': '(a nor c)', 'fn': (a,b,c) => nor(a,c) }, | |
| {'name': '(b nor c)', 'fn': (a,b,c) => nor(b,c) }, | |
| {'name': '(a or b)', 'fn': (a,b,c) => or(a,b) }, | |
| {'name': '(a or c)', 'fn': (a,b,c) => or(a,c) }, | |
| {'name': '(b or c)', 'fn': (a,b,c) => or(b,c) }, | |
| {'name': '(a nand b)', 'fn': (a,b,c) => nand(a,b) }, | |
| {'name': '(a nand c)', 'fn': (a,b,c) => nand(a,c) }, | |
| {'name': '(b nand c)', 'fn': (a,b,c) => nand(b,c) }, | |
| ]; | |
| const truetable = (fn) => { | |
| return [0, 1, 2, 3, 4, 5, 6, 7].map(x => b2i(fn(!!(x & 1), !!(x & 2), !!(x & 4)))); | |
| } | |
| const analyze_truetable = (fn) => { | |
| const tt = truetable(fn); | |
| const a1 = tt.indexOf(1); | |
| const a2 = tt.lastIndexOf(1); | |
| if (a1 === a2) return a1; | |
| else return -1; | |
| } | |
| const process_combination = (fns) => { | |
| const result = Array.from({length: 8}); | |
| for (let op of ops) { | |
| for (let ln1 = 0; ln1 < fns.length; ln1++) { | |
| for (let ln2 = ln1; ln2 < fns.length; ln2++) { | |
| const fn1 = fns[ln1]; | |
| const fn2 = fns[ln2]; | |
| const fn = (a, b, c) => op.fn(fn1.fn(a, b, c), fn2.fn(a, b, c)); | |
| const tta = analyze_truetable(fn); | |
| if (tta >= 0) { | |
| const lbl = `${fn1.name} ${op.name} ${fn2.name}`; | |
| if (!result[tta]) result[tta] = lbl; | |
| } | |
| } | |
| } | |
| } | |
| if (result.some(x => !x)) return; | |
| console.log(result); | |
| }; | |
| const perms = Combination.of(advanced_fns, 6); | |
| for (let fns_perm of perms) { | |
| const fns = [...simple_fns, ...fns_perm]; | |
| process_combination(fns); | |
| } | |
| console.log('Done.'); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment