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.
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
(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:
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
