TIN064 odvození násobení

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

V článku TIN064 ČRF, ORF, PRF se tvrdí, že primitivně rekurzivní funkce pro násobení se dá odvodit pomocí tří základních funkcí a operátorů substituce a primitivní rekurze například takto: $ R_2(o, S^2_3( R_2(I^1_1,S^1_3(s,I^2_3)), I^2_3, I^3_3)) $.

Komu to nestačí, má zde ukázku výpočtu pro $ x_1=2; x_2=3; $

 R_2(o,S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3))(3,2)
 ..R_2(o,S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3))(2,2)
 ....R_2(o,S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3))(1,2)
 ......R_2(o,S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3))(0,2)
 ........o(2)
 ........= 0
 ......= 0
 ......S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3)(0,0,2)
 ........I^2_3(0,0,2)
 ........= 0
 ........I^3_3(0,0,2)
 ........= 2
 ........R_2(I^1_1,S^1_3(s,I^2_3))(0,2)
 ..........I^1_1(2)
 ..........= 2
 ........= 2
 ......= 2
 ....= 2
 ....S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3)(1,2,2)
 ......I^2_3(1,2,2)
 ......= 2
 ......I^3_3(1,2,2)
 ......= 2
 ......R_2(I^1_1,S^1_3(s,I^2_3))(2,2)
 ........R_2(I^1_1,S^1_3(s,I^2_3))(1,2)
 ..........R_2(I^1_1,S^1_3(s,I^2_3))(0,2)
 ............I^1_1(2)
 ............= 2
 ..........= 2
 ..........S^1_3(s,I^2_3)(0,2,2)
 ............I^2_3(0,2,2)
 ............= 2
 ............s(2)
 ............= 3
 ..........= 3
 ........= 3
 ........S^1_3(s,I^2_3)(1,3,2)
 ..........I^2_3(1,3,2)
 ..........= 3
 ..........s(3)
 ..........= 4
 ........= 4
 ......= 4
 ....= 4
 ..= 4
 ..S^2_3(R_2(I^1_1,S^1_3(s,I^2_3)),I^2_3,I^3_3)(2,4,2)
 ....I^2_3(2,4,2)
 ....= 4
 ....I^3_3(2,4,2)
 ....= 2
 ....R_2(I^1_1,S^1_3(s,I^2_3))(4,2)
 ......R_2(I^1_1,S^1_3(s,I^2_3))(3,2)
 ........R_2(I^1_1,S^1_3(s,I^2_3))(2,2)
 ..........R_2(I^1_1,S^1_3(s,I^2_3))(1,2)
 ............R_2(I^1_1,S^1_3(s,I^2_3))(0,2)
 ..............I^1_1(2)
 ..............= 2
 ............= 2
 ............S^1_3(s,I^2_3)(0,2,2)
 ..............I^2_3(0,2,2)
 ..............= 2
 ..............s(2)
 ..............= 3
 ............= 3
 ..........= 3
 ..........S^1_3(s,I^2_3)(1,3,2)
 ............I^2_3(1,3,2)
 ............= 3
 ............s(3)
 ............= 4
 ..........= 4
 ........= 4
 ........S^1_3(s,I^2_3)(2,4,2)
 ..........I^2_3(2,4,2)
 ..........= 4
 ..........s(4)
 ..........= 5
 ........= 5
 ......= 5 
 ......S^1_3(s,I^2_3)(3,5,2)
 ........I^2_3(3,5,2)
 ........= 5
 ........s(5)
 ........= 6
 ......= 6
 ....= 6
 ..= 6
 = 6