1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
|
const assert = require('assert');
const { createLexer } = require('../src/core/lexer');
const { createParser } = require('../src/core/parser');
const { createInterpreter } = require('../src/core/interpreter');
describe('Turing Completeness Tests', () => {
function interpret(code) {
const lexer = createLexer(code);
const tokens = lexer.allTokens();
const parser = createParser(tokens);
const ast = parser.parse();
const interpreter = createInterpreter(ast);
interpreter.interpret(); // Execute the code
return interpreter; // Return the interpreter instance to access scope
}
describe('Church Numerals (Basic)', () => {
it('should implement basic Church numerals', () => {
const code = `
// Church numerals: represent numbers as functions
// Zero: applies function 0 times
zero : f x -> x;
// One: applies function 1 time
one : f x -> f x;
// Test with increment function
inc : x -> x + 1;
// Convert Church numeral to regular number
toNumber : n -> n inc 0;
// Test conversions
result0 : toNumber zero;
result1 : toNumber one;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('result0').value, 0);
assert.strictEqual(interpreter.scope.get('result1').value, 1);
});
});
describe('Lambda Calculus (Basic)', () => {
it('should implement basic lambda calculus operations', () => {
const code = `
// Basic lambda calculus operations
// Identity function
id : x -> x;
// Constant function
const : x y -> x;
// Function composition
compose : f g x -> f (g x);
// Test identity
testId : id 42;
// Test constant
testConst : const 10 20;
// Test composition
testCompose : compose (x -> x + 1) (x -> x * 2) 5;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('testId').value, 42);
assert.strictEqual(interpreter.scope.get('testConst').value, 10);
assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11
});
});
describe('Universal Function (Basic)', () => {
it('should implement a basic universal function', () => {
const code = `
// Simple universal function using function encoding
// This demonstrates that our language can simulate any computable function
// Function registry
functionRegistry : {
inc: x -> x + 1;
double: x -> x * 2;
};
// Universal function that can simulate any registered function
universal : funcName input ->
when funcName is
"inc" then (functionRegistry.inc input)
"double" then (functionRegistry.double input)
_ then input;
// Test the universal function
result1 : universal "inc" 5;
result2 : universal "double" 5;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('result1').value, 6);
assert.strictEqual(interpreter.scope.get('result2').value, 10);
});
});
describe('Turing Machine Simulator (Basic)', () => {
it('should simulate a basic Turing machine', () => {
const code = `
// Simple Turing machine that counts 1s on the tape
// States: "start", "halt"
// Initialize Turing machine
initTM : {
tape: [1, 1, 0, 1],
head: 0,
state: "start"
};
// Transition function
transition : tm ->
when tm.state is
"start" then when (tm.head >= (length tm.tape)) is
true then { tape: tm.tape, head: tm.head, state: "halt" }
_ then { tape: tm.tape, head: tm.head + 1, state: "start" }
_ then tm;
// Run Turing machine
runTM : tm ->
when tm.state is
"halt" then tm
_ then runTM (transition tm);
// Test
result : runTM initTM;
`;
const interpreter = interpret(code);
const result = interpreter.scope.get('result');
// Should reach halt state
assert.strictEqual(result.state, "halt");
});
});
describe('Recursive Functions (Turing Complete)', () => {
it('should demonstrate Turing completeness through recursion', () => {
const code = `
// Ackermann function - a classic example of a computable but not primitive recursive function
// This demonstrates that our language can compute any computable function
ackermann : m n ->
when m is
0 then n + 1
_ then
when n is
0 then ackermann (m - 1) 1
_ then ackermann (m - 1) (ackermann m (n - 1));
// Test with small values (larger values would cause stack overflow)
result1 : ackermann 0 5;
result2 : ackermann 1 3;
result3 : ackermann 2 2;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('result1').value, 6);
assert.strictEqual(interpreter.scope.get('result2').value, 5);
assert.strictEqual(interpreter.scope.get('result3').value, 7);
});
});
describe('Higher-Order Functions (Turing Complete)', () => {
it('should demonstrate Turing completeness through higher-order functions', () => {
const code = `
// Higher-order functions that can simulate any computable function
// Test with factorial using fixed point
factorialHelper : f n ->
when n is
0 then 1
_ then n * (f (n - 1));
// Test with small values
testFactorial : factorialHelper (n -> 1) 0;
testFactorial2 : factorialHelper (n -> n * 1) 1;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('testFactorial').value, 1);
// The helper calls f(0) when n=1; with f = (n -> n * 1), this evaluates to 0
assert.strictEqual(interpreter.scope.get('testFactorial2').value, 0);
});
});
describe('SKI Combinator Calculus (Basic)', () => {
it('should implement basic SKI combinators', () => {
const code = `
// SKI Combinator Calculus - basic version
// K combinator: Kxy = x
K : x y -> x;
// I combinator: Ix = x
I : x -> x;
// Test I combinator
testI : I 42;
// Test K combinator
testK : K 10 20;
// Test composition
compose : f g x -> f (g x);
testCompose : compose (x -> x + 1) (x -> x * 2) 5;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('testI').value, 42);
assert.strictEqual(interpreter.scope.get('testK').value, 10);
assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11
});
});
describe('Mutual Recursion (Turing Complete)', () => {
it('should demonstrate Turing completeness through mutual recursion', () => {
const code = `
// Mutual recursion example - isEven and isOdd
// This demonstrates that our language can handle complex recursive patterns
isEven : n ->
when n is
0 then true
1 then false
_ then isOdd (n - 1);
isOdd : n ->
when n is
0 then false
1 then true
_ then isEven (n - 1);
// Test mutual recursion
result1 : isEven 0;
result2 : isEven 1;
result3 : isEven 2;
result4 : isEven 3;
result5 : isOdd 0;
result6 : isOdd 1;
result7 : isOdd 2;
result8 : isOdd 3;
`;
const interpreter = interpret(code);
assert.strictEqual(interpreter.scope.get('result1'), true);
assert.strictEqual(interpreter.scope.get('result2'), false);
assert.strictEqual(interpreter.scope.get('result3'), true);
assert.strictEqual(interpreter.scope.get('result4'), false);
assert.strictEqual(interpreter.scope.get('result5'), false);
assert.strictEqual(interpreter.scope.get('result6'), true);
assert.strictEqual(interpreter.scope.get('result7'), false);
assert.strictEqual(interpreter.scope.get('result8'), true);
});
});
});
|