1)
Write down the axioms schema and the three
shortest axioms in the tq-system
R: xT-Qx
is an axiom, whenever x is a hyphen string.
-t-q-
--t-q--
---t-q---
2)
Write down the sole rule of inference for the
tq-system and apply it to the well-formed string -----t-----q-----
R:
Rule: Suppose that x, y and z are all hyphen-strings. And suppose that xTyQz is
an old theorem. Then, xTy-qzx a new theorem.
(1) -----t-----q----- axiom
(2) -----t------q---------- from (1) using the rule
3)
Reasoning in I-mode, argue that the string you
produced in the previous item is not a theorem in the tq-system
R: It
cannot be a theorem because 5x6 != 11.
4)
Working in M-mode, show that -----t ---q
--------------- is a theorem in the tq-system.
R: Use
the rule to go back and find the axiom, if it is an axiom, than it is a
theorem.
(1) -----t---q--------------- theorem
(2) -----t--q---------- from (1) using the
inverse of the rule
(3) -----t-q----- from (2) using the
inverse of the rule
-----t-q------ = xT-Qx
From this we ca conclude that ------t---q--------------- is a theorem in
the tq-system.
5)
What are the two rules of C-system
R:
1) Suppose
x, y and z are hyphens-strings. If x-ty-qz is a theorem then Cz is a theorem.
2) Suppose that x, y and z are all hyphen-strings. And suppose that xTyQz is an old theorem. Then, xTy-qzx a new theorem.
6)
Working within the C-system, argue that
C-------- is a theorem of the system.
R: --t-q-- axiom
(2) --t--q---- from axiom using rule 2
(3) --t---q----- from (2) using rule 2
(4) --t----q-------- from (3) using rule 2
(5) C-------- from (4) using rule 1
7)
Does adding the following rule to the C-system
constitute a Post production system for determining primes? Please explaining
your response. Suppose x is a hyphen-string. If Cx is not a theorem, then Px is
a theorem.
R: No, because the rule does not entail a purely typographical operation.
8)
Hofstadter writes. When a figure or “positive
space” (e.g., human form, or a letter, or a still life) is drawn inside a
frame,an unavoidable consequence is that its complementary shape – also called
the “ground” , or “background”, or “negative space” – has also been drawn. According to this view, the quiche pan shown
below that I computationally rendered would be considered negative space.
Explain how this is so.
R: The
drawn consist in the black space and the withe space is the ground.
9)
Consider the A-system as defined by the
following axiom and theorem. Axiom A-- , Rule: suppose that x is a
hyphen-string, If Ax is a theorem , so is Ax--
a)
Show that A -------- is a theorem of the
A-system by working within the system
R: (1)
A - - axiom
(2) A - - - - from (1) using the rule
I
(3) A - - - - - - from (2) using the rule I
(4) A -------- from(3) using the rule I
b)
Specify a decision procedure for determining theorem
hood in the A-system
R: Suppose
you have Ax, if you can use the rule to go back to A -- (The only axiom) you
can say that Ax is a theorem.
c)
Provide an I-mode argument that the string
A------------ is not a theorem of the A-system
R: All
theorems in the A-system have an even number of hyphens.
d)
What subset of the natural numbers do you think
it was my intent to capture with the A-system
R:
All even numbers.
10)
Consider the as yet to be formally defined
B-system which you should imagine is intended to capture precisely all of the
natural numbers that the A-system does not capture.
a)
Propose, by analogy with the rule on page 66 of
GEB, an invalid rule for producing theorems in the B-system.
R: Suppose x is a
hyphen-string. If Ax is not a theorem, then Bx is a theorem.
b)
Define a (valid) Post production system for the
B-system in terms of one axiom and one rule
R: Axiom: B-
Rule I: Suppose that x is a hyphen-string.
If Bx is a theorem, so is Bx--
c)
Derive B----------- within the B-system.
R: (1) B- axiom
(2) B--- from(1) using the rule I
(3) B----- from (2) using the
rule I
(4) B------- from (3) using
the rule I
(5) B--------- from (4) using
the rule I
(6) B----------- from(5)
using the rule I
d)
What subset of the natural numbers does the
B-system capture?
R: All odd numbers.
11)
Under interpretation, what does the A-system
theorem A -------- say? Under interpretation, what does the B-system theorem
B----------- say?
R:
Say that 8 is an even number and 11 is a odd number.
12)
What does mean for a set to be “recursively enumerable”?
What does it mean for a set to be “recursive”?
R: Recursively
Enumerable: Means that it can be generated according to typographical rules.
Recursive: A set is recursive if you
can write a program that tells you whether the given input is in the set or
not.
13)
Argue that the set of even number is recursively
enumerable.
R:
Using the A-system you can produce every even number. The A-system use a
typographical rule
14)
Argue that the set of even number is recursive
R: It is recursively enumerable and its complement (odd numbers) is recursive because you can use B-system to get all odd numbers.
15)
Argue that the set of prime numbers is
recursively enumerable.
R:You could use rule of the Px-system to get all recursive enumerable.
16)
Argue that the set of prime numbers is
recursive.
R: It is recursively enumerable and its complement (odd numbers) is recursive because you can use C- system to the rest of the numbers.
17)
In a sentence or two, explain why you think that
I am not asking you in this problem set to derive something lime P----- within
the P-system?
R: Because
the P system it is not a formal system that have a typographical rule.
18)
Consider the following Post production system, a
system that we will call the @?- system:
AXIOM: @ | | - ||| -
Rules: Suppose x is a string made up of
zero or more symbols drawm from the set { @ , - , |} then:
1: if you have x-||-|||, you can add –
2: if you have x-|||-||, you can add –
3: if you have x|-||-||, you can add |
4: if you have x|-|||-|, you can add |
5: if you have x||-||-|, you can add |
6: if you have x|-|||-, you can add |
7: if you have x|||-||-, you can add |
8: you can replace @ by C
9: you can replace @ by G
10: you can replace @ by D
11: you can replace C| by CD
12y you can replace C- by CV
13: you can replace V| by VW
14: you can replace V- by VD
15: you can replace D| by DE
16: you can replace D- by DW
17: you can replace W| by WF
18: you can replace W- by WE
19: you can replace E| by EX
20: you can replace E- by EF
21: you can replace F| by FG
22: you can replace F- by FX
23: you can replace X| by XY
24: you can replace X- by XG
25: you can replace G| by GA
26: you can replace G- by GY
27: you can replace Y| by YZ
28: you can replace Y- by YA
29: you can replace A| by AB
30: you can replace A- by AZ
31: you can replace Z| by ZC
32: you can replace Z- by ZB
33: you can replace B| by BV
34: you can replace B- by BC
a)
How many axioms in the system? How many rules in
the system? How many theorems in the system?
R: 1 Axiom. 34 Rules. Infinite theorems.
b)
Show that @||-|||-||-|||- is a theorem of the
@|- system by performing a derivation within the system.
R: @||-|||- axiom
(2) @||-|||-| from(1) by rule 6
(3) @||-|||-|| from(2) by rule
4
(4) @||-|||-||- from(3) by
rule 2
(5)@||-|||-||-| from(4) by
rule 7
(6)@||-|||-||-|| from(5) by
rule 5
(7)@||-|||-||-||| from(6) by
rule 3
(8) @||-|||-||-|||- from(7) by
rule 1
c)
Show that CDEFGABC
is a theorem of the @|- system by
performing a derivation within the system
R: (1) @||-|||- axiom
(2) C||-|||- from (1) by rule 8
(3) CD|-|||- from (2) by rule
11
(4) CDE-|||- from (3) by rule
15
(5)CDEF|||- from (4) by rule
20
(6)CDEFG||-from (5) by rule 21
(7)CDEFGA|-from (6) by rule 25
(8)CDEFGAB - from (7) by rule
29
(9) CDEFGABC from (8) by rule
34
d)
Show that GABCDEXG
is a theorem of the @|-system by
performing a derivation within the system
R: (1) @||-|||- axiom
(2) G||-|||- from (1) by rule 9
(3) GA|-|||- from (2) by rule
25
(4) GAB-|||- from (3) by rule
29
(5)GABC|||- from (4) by rule
34
(6)GABCD||-from (5) by rule 11
(7)GABCDE|-from (6) by rule 15
(8)GABCDEX - from (7) by rule
19
(9) GABCDEXG from (8) by rule
24
e)
Show that DEXGABVD
is a theorem of the @|-system by performing a derivation within the system
R: (1) @||-|||- axiom
(2) D||-|||- from (1) by rule 10
(3) DE|-|||- from (2) by rule
15
(4) DEX-|||- from (3) by rule
19
(5)DEXG|||- from (4) by rule
24
(6)DEXGA||-from (5) by rule 25
(7)DEXGAB|-from (6) by rule 29
(8)DEXGABV - from (7) by rule
33
(9) DEXGABVD from (8) by rule
14
f)
What do you think I had in mind when I invented
this system?
R:Generate musical scales.
Click here to download the PDF
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg "Bar 3")
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg){kind=link}