Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: CHAITAN'S POWERSET!
Replies: 3   Last Post: Mar 6, 2013 1:24 AM

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,495 Registered: 5/20/10
CHAITAN'S POWERSET!
Posted: Jan 16, 2013 3:48 PM

INPUT 1 2 3 4 5 6 7 8 9 10 ...
=============================
TM1 H L H H H L L L L L ...
TM2 H H H H H H H H H H ...
TM3 H L L L L L L L L L ...
TM4 L H L H L H L H L H ...
...
If TM1(1) Halts then 1 e POWERSET_1
If TM1(2) Loops then 2 !e POWERSET_1
...
If TM2(1) Halts then 1 e POWERSET_2
If TM2(2) Halts then 2 e POWERSET_2
...

1 <=> {1,3,4,5,...}
2 <=> {1,2,3,4,5,...}
3 <=> {1}
4 <=> {2,4,6,8,10...}
| | | | |
TM4 LHLHLHLHLH ...

Instead of constructing an UN-COMPUTABLE REAL
And using CHAITANS OMEGA to argue computable reals are UN-COUNTABLE

YOU CAN CONSTRUCT AN ACTUAL SEMI-DECIDABLE
POWERSET OF N!

Herc
--
S: if stops(S) gosub S
G. GREENE: this proves stops() must be un-computable!

Date Subject Author
1/16/13 Graham Cooper
3/5/13 Charlie-Boo
3/5/13 Bill Taylor
3/6/13 Graham Cooper