Entries by Clifford Wolf

Nick Sibicky recently uploaded three videos to his youtube channel of him playing Hidden Move Go with Andrew Jackson. As someone interested in Go and AI I think Hidden Move Go would be an extremely interesting game for serious competitions, because unlike plain Go, Hidden Move Go is an imperfect information game. However, as Nick explains in the second half of his third video, there are some weird corner cases in Hidden Move Go that prevent it from being a game played in competitions. In the following paragraphs I'd like to outline a set of rules that are different from the rules of Hidden Move Go, but equivalent for almost all game situations. As far as I can tell this rules avoid the corner cases.

The big difference to regular Hidden Move Go is that in this version the hidden moves are not considered on the board before they are revealed. There is no "hidden board" with the complete information. Instead revealing a hidden move is equivalent to making an extra move in the current turn. Revealing a hidden move can be used to undo the other players last move, creating the illusion that the stone was always there and that the opponents last move was therefore illegal.

The Rules

This rules are based on AGA rules, but could easily be adopted to Japanese or Chinese rules.

Before the first regular move is played each player writes his three hidden moves on three index cards. (The cards are kept so that the opponent can not see the hidden moves. Depending on the setting the players may chose to show their hidden moves to spectators.)

Each turn the current player may reveal any of his or her hidden moves before playing the regular move. A player may not reveal a hidden move if (1) the other player already has a stone on the position and it was not the last stone the other player has played or (2) the other player already has a stone on the position and the current player has already revealed other hidden moves in this turn or (3) revealing the hidden move would be suicidal. The hidden move may capture stones.

For each revealed move the player places the corresponding stone on the board. If the revealed move is on the position where the other player placed his last stone, then the current player places his stone on that position and gives the other players stone back to the other player. This ends the players move and the other player can chose a different move. If the "illegal" move captured some stones then the other player has to put them back on the board on his own time before making a new move.

Revealing a hidden move may create a board position that existed before, but the regular move played afterwards must create a new board position. It is illegal to recreate an earlier board position by revealing a hidden move and then pass on the regular move.

A card with hidden move can only be revealed once. But it is legal to write the same move on multiple cards and use the second hidden move after the first revealed stone is captured.

At the end of the game each player has to reveal their remaining (unused) hidden moves, if they have any, and give a passing stone for each of them to their opponent.

Discussion of some differences to regular Hidden Move Go

In regular Hidden Move Go a hidden move must be revealed when the opponents move would be suicidal because of the hidden move. In this version the suicidal move is OK and the stones can be captured by the other player by revealing the hidden move.

In a Ko fight it is possible that one player has a hidden move in one of the eyes. This would allow the player with the hidden move to fix the Ko at any time. Either by fixing with the hidden move, or by capturing with the hidden move and then fixing with the regular move that follows. That the same position as the hidden move was possibly played and captured many times before does not matter.

With this rules it is not possible to capture a hidden stone.

In this rules it is possible to simply not reveal a hidden stone in situation where one would have to reveal it in the regular rules. One possible motivation would be when the hidden stone is not very useful and the player considers it more advantageous to use the unrevealed stone to "bluff" somewhere else on the board.

When both players put a hidden move on the same position then whoever reveals it first has a stone on that position. When that stone is captured the other player is again free to reveal his hidden move and put his hidden stone on that position.

Interpretation and conclusion

With this set of rules I like to think of the hidden moves as stones hiding inside the board (or military units hiding in the woods, if you are like to think of Go stones as military units). Other stones do not interact with them in any way until they come out of hiding. But in some cases it would become illegal for them to come out of hiding and thus are captured in hiding, which fits nicely with the passing stones for unused hidden moves.

In the large majority of games and game positions I think this rules would be equivalent to the regular rules of Hidden Move Go. There might of course be some positions where the regular rules would produce an "epic moment" and this rules won't, and vice versa. I'll leave it to you to discuss this pros and cons below in the comments.

I have not spend an enormous amount of time thinking through all the possible corner cases, so please feel free to leave a comment below if you think you have found that some weird situations for which my rules may be problematic. I'd be happy to discuss them and modify this blog post to work around the issues, if possible.

I did not blog for a while. Here are some updates on what I've been up to in the 15 months since my last blog post:

I've been working on Yosys and formal verification a lot.

In 2016 I've been visiting EasterHack 2016 and gave a long talk about Verilog Synthesis and Formal Verification with Yosys. I've also been to ORCONF 2016 and 33C3 and gave a shorter talk focusing on Formal Verification with Yosys. (I've also been to FOSDEM 2016 and gave a slightly updated version of my 32C3 talk on my Free and Open Source Verilog-to-Bitstream Flow for iCE40 FPGAs.

Earlier this year I've been invited to JKU to give a talk about my current work, focusing on SymbiYosys.

Also in 2016 I finally released PonyLink, a fast single-wire bidirectional interface for connecting FPGAs. I wrote this some time in 2015 but never found the time to clean it up and release it until last summer.

In November 2016 I've been to Berkeley, CA and had many interesting meetings with some great people there (thanks Alan for inviting me). I also met some of the RISC-V crowd in in Berkeley (Aspire Lab at UCB) and San Francisco (SiFive). As a consequence of this I'm now working on riscv-formal, a framework for formally verifying ISA compliance of RISC-V processor cores.

What else? The IcoBoard is finally available for sale online.

Oh, and we won Best Paper Award at ICCAD 2016 with our paper on malicious design flows that inject trojans during synthesis.

Some of the stuff I did in 2015:

Yosys now has a powerful formal verification flow based around the SMT2 file format: yosys-smtbmc. I've also made a presentation on computational complexity, SAT/SMT solving, and that new verification flow: http://www.clifford.at/papers/2015/yosys-smt-bmc/

I have written a documentation of the iCE40 bit-stream format and created a Yosys-based open source synthesis flow for that FPGA family (Project IceStorm): http://www.clifford.at/icestorm/

I have created PicoRV32, one of the smallest RISC-V CPU cores out there: https://github.com/cliffordwolf/picorv32

I've released SimpleVOut, A Simple FPGA Core for Creating VGA/DVI/HDMI/OpenLDI Signals: https://github.com/cliffordwolf/SimpleVOut

I have participated in this years Google Summer of Code as a mentor. Unfortunately the student I mentored dropped out shortly after the midterms. But the publicity from the Google Summer of Code helped me find Cotton Seed and some other very interesting people (or rather helped them find me). Cotton is the author of Arachne-pnr, the place and route tool used in the IceStorm FPGA flow.

I bought a Ninebot One, learned how to ride it, and then learned the hard way to only ride it wearing protective gear: I broke both my wrists and my right elbow in an accident. Luckily I recovered very quickly.

The video recordings on the (german) electronics lectures I gave at Metalab went online this year, over 100 videos : https://metalab.at/wiki/Elektronik_Kurs#Videoaufzeichnung

For Yosys I was long stuck with std::set<> and std::map<> as primary container classes because one of the goals of Yosys is to produce identical outputs for the same input across all compilers and architectures. (A goal that is not reached yet btw, but I'm working towards it.) The std::unordered_* versions of those containers don't even make guarantees about identical order of iteration between two processes executing the same code. For my taste it is to easy to make a crucial programming mistake and accidentally iterate over one of those containers in a situation where the order of iteration has a subtle influence on the program output. So I've created my own containers that have the guarantees I need for Yosys. My hashlib::dict<> is a replacement for std::unordered_map<> and my hashlib::pool<> is a replacement for std::unordered_set<>. (My containers also require the programmer to be more explicit when using pointers as keys and they utilize an interface for creating hash values that integrates better with Yosys's core data structures than the std::hash()-scheme does.)

To my surprise my straight-forward textbook implementation of a hash table is significantly -- sometimes over 2x (!) -- faster than the STL versions of the same containers. I guess it pays off if you do not design your data structures around strange interfaces such as bucket iterators.. (Did anyone ever use them, btw?)

The picture below shows the results of this simple benchmark (also includes my hashlib.h library). Because I replace the ordered STL containers directly with my unordered versions, I also included the ordered STL containers in the benchmark. The labels "sparse" and "dense" in the figures below refer to the used alphabet. The "dense" alphabets are slightly easier to hash. For each of the 240 data points the benchmark executed 20000000 operations (insert, update or delete), first filling the container to the specified size (in number of elements) and then inserting and deleting while keeping the size around that value (within +/- 1000 entries and +/- 10%). In the tests for the map containers int was used as value type. (click image to enlarge)



PS: Clang version: 3.4-1ubuntu3, GCC version: 4.8.2-19ubuntu1

I bought an Acer Chromebook 13 CB5-311-T6R7 (the one with the NVidia Tegra K1 ARM CPU) to run it in a dual-boot configuration with Chrome OS and Ubuntu. I've used a slightly modified version of the modified chrubuntu script from here to install ubuntu. My version of the scripts and a writeup of the install procedure can be found here.

Update 2015-01-20: I have now updated my install script to address the freeze up issue discussed in the comments below. See my comment for the details of the fix used.

Update 2015-08-28: I have now updated my install script to use the current NVidia "Tegra for Linux" release, Tegra124_Linux_R21.4.0.

After over 8 years of service my old server had a fatal crash three days ago. The disk controller died and killed both disks (RAID1) in the process. Fortunately my backup strategy worked like a charm and I only lost about 6 hours of incoming email (so if you sent me a mail in the morning of Thu 4th December 2014: please try again).

Following an ancient tradition (of over 15 years) the new server is called phoenix.clifford.at, like the ones before it.

I have a backup of all data from the old machine, but I decided not to re-setup everything that ran on the old server. Especially I did not re-setup the shell logins I gave away over the course of the last 15 years. I also decided not to re-setup the services related to ROCK Linux. Please contact me if you had data on the old server that you want back or had a shell account that you were still using..

BTW: The backup solution I'm using is a simple shell script I wrote over 10 years ago and am using ever since. I've now put it on github, just in case anyone of you is interested: https://github.com/cliffordwolf/rsbak3

I own a TomTom Start navigation system. A few weeks ago it suddenly stopped working: It simply would not power on. Yesterday I took it apart to see if there was something I could do to fix it, or harvest some parts if there was nothing I could do. I took it apart but left all components connected to each other, with the exception of the speaker which I had to unplug in order to get the electronics out of the case. Most of the electronics are behind a soldered shield and there where no visible faults on the parts that where freely accessible. So I started by measuring the supply voltage: The battery was still fully charged. At this point I had an idea: What if the TomTom, as many devices do these days, has a small microcontroller that is always powered on and handles stuff like the power-up sequence? What if this microcontroller got stuck? I simply unplugged the battery and plugged it back in. The device booted right away.

So if you have a TomTom and encounter such a problem: don't just throw it away. Instead try unconnecting and reconnecting the battery from the motherboard first. However: It might not be easy to take the device apart and reassemble it if you don't have experience with that kind of stuff. Just remember: You have nothing to loose. Hint: There is a screw hidden behind the hinge for the vacuum cup.

Remains one question: Is this really a bug or planned obsolescence? If done right, it is almost impossible to have such a crucial bug in such a simple microcontroller application. That's why microcontrollers usually have features such as brown-out detection and hardware watchdog timers: so that you can write firmware for them that never hangs, even if there is a critical bug in it or the supply voltage has crazy transients. So either they had extremely bad luck with this particular design, or they designed it to fail approximately one year after the first power-on.

I recently bought a RIGOL DS2072 Oscilloscope. This is not a review but let me just say this: For the price this scope is awesome!

Of course I want to control my new scope from Linux. There are some articles online how to talk to a DS1052E [1, 2], but I haven't found anything that can be applied directly to the DS2072. When I connect the DS2072 via USB with the PC, the scope gets enumerated as PTP (Picture Transfer Protocol, a USB protocol for cameras) device and I have not figured out how to put it in a different mode. But the DS2072 also has an ethernet port and I managed to interface with the scope via the VISA VXI Protocol using the LibreVISA library.

So I wrote a small command-line tool that provides a shell that accepts commands from the terminal, sends them to the scope, reads back the results, and prints then to the terminal. The sourcecode of the program can be downloaded (or checked out) from this Subversion link:

http://svn.clifford.at/handicraft/2013/rigol-ds2000-shell/

The README file contains some instructions on how to build it and an example session demonstrating various features of the program.

Very recently a licence key generator for this scopes was published [3]. I have also included an interface to this generator that allows for easy unlocking of features in such scopes. Just connect to the scope an type 'install dsa9' to convert to a DS2202 with all options enabled (all commands are case-insensitive):

$ ./rigol-ds2000-shell TCPIP::192.168.0.123::INSTR

Connected to RIGOL TECHNOLOGIES,DS2072,DS2A152701234,00.01.01.
Type 'help' for help.

DS2A152701234> INSTALL DSA9
*** serial: DS2A152701234
*** options: DSA9
*** lic1-code: 12345678901234
*** lic2-code: 56789012345678
*** target-code: 90123456789012345678901234567
*** ----------------------------------------------------
*** your-license-key: 8901234-5678901-2345678-9012345
*** ----------------------------------------------------
> :SYSTEM:OPTION:INSTALL 8901234567890123456789012345

Of course input redirection (< filename) can be used to read commands from a file. For example, the following command file sets up the scope, waits for a trigger and then downloads the recorded data (as 5 mio. data points) to an ascii file.

*RST
SLEEP 1

:CHANNEL1:PROBE 10
:CHANNEL1:OFFSET 0
:CHANNEL1:SCALE 0.5
:CHANNEL1:COUPLING AC
:CHANNEL2:DISPLAY OFF
:TIMEBASE:SCALE 1e-4
:ACQUIRE:MDEPTH 14000000
SLEEP 3

:SINGLE
WAIT

:WAVEFORM:MODE RAW
:WAVEFORM:POINTS 5000000
DOWNLOAD_TXT waveform.txt

The commands starting with * or : are SCPI commands as described in the DS2000 Programming Guide. The other commands are native rigol-ds2000-shell commands and are described in the output of the HELP command.

A possible usage scenario is to call rigol-ds2000-shell from another program (such as GNU Octave, SciLab, Matlab, R, Python, etc.) and read back the written files once rigol-ds2000-shell is finished. As downloading large waveforms usually takes a while, the overhead for calling a separate binary is negligible.

Another usage scenario is to use rigol-ds2000-shell interactively to figure out the correct command sequences and then write a custom tool for whatever you want to do with your scope, possibly reusing some of the code from rigol-ds2000-shell.

Ich werde in den kommenden zwei monaten jeweils einen LUGA Vortrag halten (Achtung: fuer die LUGA unueblich sind die Termine Donnerstags):

• Do, 23.5.2013 -- High-Performance-Computing mit GPUs
  
• Do, 27.6.2013 -- OpenSCAD und QCad/LibreCAD
  

Wie viele meiner Leser wissen werden halte ich im Metalab auch einen Elektronik Kurs zum dem schon laenger Videos versprochen sind. Diese koennten moeglicherweise bald online gehen. Wer nicht warten will kann sich durch folgende bunt gemischte Videoempfehlungen durchclicken:

• LLVM 2012 European Conference
  Insbesondere der "Tablegen Deep Dive" Vortrag von Reed Kotler hat mir besonders gefallen. Da wurden viele meiner lang anstehenden Fragen zu TableGen geklaert. Die Folien zum Workshop "Building a backend in 24 hours" von Anton Korobeynikov fand ich ebenfalls sehr aufschlussreich.
  
  
• LLVM 2012 US Conference
  Da kann ich besonders "MemorySanitizer, ThreadSanitizer" von Kostya Serebryany und "Zero-Cost Abstractions" von Chandler Carruth empfehlen.
  
  
• GTC on Demand
  Da sind so viele Videos zu GPU programmierung das es sehr schwierig ist die wirklich guten zu finden. Die Optimization Talks von Paulius Micikevicius sind ausgezeichnet. Und "Better Performance at Lower Occupancy" von Vasily Volkov ist quasi ein Klassiker. Die Videos von der GTC 2013 sollten bald online gehen (die GTC 2013 war von 18. bis 21. Maerz und lt. Website wollten sie die Videos nach 30 tagen online stellen).
  
  
• 29C3 - Not My Department
  Die Videos zum letzten chaos communication congress liegen auf media.ccc.de. Ich fand insbesondere den Vortrag zu Low-Cost Chip Mi­cro­prob­ing von dexter und nohl interessant. (Ich erspare euch jetzt mal das gejammer darueber, dass es am kongress zu wenig technische talks gibt.)
  

Falls jemand weitere Vortragsvideos empfehlen moechte freue ich mich ueber entsprechende Kommentare!

I'm back from 29C3 and it was awesome! Lessons learned for the next year:

• You can not escape the Hackerpest!
  


• Pack at least a full set of clothes for every day (including new trousers for every day), if you plan to spend even a second in the smokers area.


• Bring heavy shoes for walking around outside and light shoes for walking around at CCH.


• Have a look at the Workshop schedule beforehand and use a schedule app (or write one) that includes the workshops and other auxiliary events.


• Don't be such a geek and talk to more people and ask more questions at the assemblies.


• Bring more stuff if you have additional space in your case.


• Bring an extra bag to carry stuff around at the conference.


• If you can afford it, book a room at the Radisson Blu (the hotel directly connected to the CCH).


• Prepare yourself to explain all your ongoing projects in less than 5 minutes.


• Arrive at day 0 or even day -1.

(Bild: MagicShifter by Wizard23)

This is a quick write-up of the steps necessary to install Xilinx ISE 14.2 / Vivado 2012.2 on Kubuntu (Ubuntu) 12.04.1 LTS (64bit). First of all lets be said that Xilinx does not officially support Kubuntu/Ubuntu as Platform. It might work or not but don't blame Xilinx if it doesn't...

First of all extract the Xilinx_ISE_DS_Lin_14.2_P.28xd.3.0.tar and execute xsetup as root. Install everything in the default directory (/opt/Xilinx). This may take a while.

When you want to start ISE, Vivado or Vivado_HLS, first execute the command "source /opt/Xilinx/14.2/ISE_DS/settings64.sh" in your shell to set PATH and other environment variables. Note that the PATH set by this command does not include the PATH to docnav (/opt/Xilinx/DocNav/) and viavdo_hls (/opt/Xilinx/Vivado_HLS/2012.2/bin/). This commands still must be called using the full path. I'm not sure why Xilinx decided to not add this directories to the PATH environment variable.

Xilinx ISE comes with its own version of some system libraries (like libstdc++). The settings64.sh script adds the directories containing this libraries to the LD_LIBRARY_PATH environment variable. This has the effect that after you have sourced this script in your shell you can't exectue many system commands in this shell anymore. So I recomment working with two shells: One for the Xilinx commands and a 2nd one for the system commands.

The tools are using kfmclient, google-chrome and acroread to open web sites and display PDF files. I have neither command on my system and even if I had just calling them would not work as one would have to reset LD_LIBRARY_PATH in order to execute them. So I had to add some wrapper scripts that are calling the appropriate tools with a cleaned-up environment.

--- /usr/local/bin/kfmclient ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
echo "KFMCLIENT: $*" >&2
[ "$1" = openURL ] && chromium-browser "$2" &
exit 0

--- /usr/local/bin/google-chrome ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
chromium-browser "$@" &
exit 0

--- /usr/local/bin/acroread ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
okular "$@" &
exit 0

(In case you are wondering: The ISE tools are using kfmclient to open web-pages and the Vivado tools are directly trying to call a web-browser executable. Vivado tries "google-chrome" first, followed by "firefox" and a short list of others.)

Of course one can also consider installing such wrapper scripts in one of the Xilinx bin directories. I've decided to install the directly in /usr/local/bin/ for various resons that might not apply to everyone..

In order to get Vivado_HLS running two additional steps are required. First we need to copy crt1.o, crti.o and crtn.o to a place where the gcc that comes with Vivado_HLS can find it:

sudo cp /usr/lib/x86_64-linux-gnu/crt[1in].o \
/opt/Xilinx/Vivado_HLS/2012.2/Linux_x86_64/tools/gcc/lib/gcc/

Unfortunately the SystemC C++ code generated by Vivado_HLS suffers from the so-called "c++ static initialization order fiasco" (just google the term if you are not familiar with it). To make it short: The SystemC code generated by Vivado_HLS depends on undefined C++ behavior which leads to strange problems on some platforms while others are not effected (depending on the initialization order of static objects in different compilation units). This is a serious problem and as of this writing I'm in contact with Xilinx support in order to resolve it.

Note that this Problem does not effect the generated Verilog and VHDL RTL code. It only effects the SystemC module that is generated for simulation purposes only.

I've recorded a short (2:41) screencast in which I demonstrate the problem and a possible solution (i.e. using the "sc_dt::Log_*" enum to initialize static variables instead of using the global "SC_LOGIC_*" objects):
http://www.youtube.com/watch?v=HqDpRUFff94

Another work-around is to change one of the SystemC headers so that every compilation unit gets its private version of the SC_LOGIC_* objects, thus resolving the initialization order problem (the initialization order of static objects within a compilation unit is defined in C++):

--- Vivado_HLS/2012.2/Linux_x86_64/tools/systemc/include/sysc/datatypes/bit/sc_logic.h
+++ Vivado_HLS/2012.2/Linux_x86_64/tools/systemc/include/sysc/datatypes/bit/sc_logic.h
@@ -593,10 +593,17 @@
 }
 
 
+#if 0
 extern const sc_logic SC_LOGIC_0;
 extern const sc_logic SC_LOGIC_1;
 extern const sc_logic SC_LOGIC_Z;
 extern const sc_logic SC_LOGIC_X;
+#else
+static const sc_logic SC_LOGIC_0 = Log_0;
+static const sc_logic SC_LOGIC_1 = Log_1;
+static const sc_logic SC_LOGIC_Z = Log_Z;
+static const sc_logic SC_LOGIC_X = Log_X;
+#endif
 
 // #ifdef SC_DT_DEPRECATED
 extern const sc_logic sc_logic_0;

This is of course the prefered solution if you want to get Vivado_HLS running as it does not require any changes to the generated SystemC modules. It is not a nice final solution. But it makes the whole thing work without somehow automatically patching all generated SystemC modules.

I haven't tried the cable drivers (I'm using my own software for JTAG programming) and certainly haven't tried all the tools that are part of Xilinx ISE 14.2 / Vivado 2012.2. But I think I've covered the most important topics in my tests and with the above hacks I have the parts I need for my work running just fine.

I hope this write-up is of help for some of my readers. Of course there is no warranty of any kind from my side and Xilinx does not support their software on Kubuntu/Ubuntu either. So don't say you have not been warned..

Morgen Abend, Fr. 30.3.2012 ab 19:00, startet der zweite Turnus des Metalab Elektronikkurs. In aller kuerze hier einfach noch mal ein copy&paste der Ankündigung:

Das Metalab (http://metalab.at/) veranstaltet einen kostenlosen
Elektronikkurs. Der erste Kursabend, der zugleich die Vorbesprechung zur
Koordination der weiteren Termine darstellt, findet am Freitag dem
30.3.2012 ab 19:00 im Metalab, Rathausstrasse 6, 1010 Wien statt.

Detailierte Informationen zu den Kursinhalten und zum Ablauf sowie eine
PDF-Version des Skriptums sind auf der Homepage des Kurses zu finden:

https://metalab.at/wiki/Elektronik_Kurs

Für diejenigen, die die Grundlagen schon beherrschen und sich primär für
die Fortgeschrittenen-Themen interessieren, ist auch ein späterer Einstieg
in den Kurs möglich. Der Besuch des ersten Kursabends ist aber wegen der
Vorbesprechung auf jeden Fall empfohlen.

Zielgruppe sind alle Menschen die sich für Elektronik interessieren und
elektronische Schaltungen verstehen und selbst entwickeln wollen.

Ich freue mich auf möglichst viele TeilnehmerInnen!

Nachdem ich gerade mein Android Handy neu aufsetzen musste hier eine kleine Liste von Android Apps die ich gut finde und auf meinem Handset installiert habe (neben Apps wie YouTube und Google Maps die schon Teil der Factory Defaults sind):

• AnkiDroid
  
• ConnectBot
  
• Barcode Scanner
  
• Google Goggles
  
• CamScanner
  
• Adobe Reader
  
• Google Reader
  
• TuneIn Radio
  
• Twitter
  

Und bis VLC for Android fertig ist verwende ich erst mal RockPlayer Lite.

Kommentare mit weiteren App-Empfehlungen sind natuerlich herzlich willkommen!

This American Life hat vor fast zwei Wochen die hervorragend gemachte Folge "When Patents Attack!" ausgestrahlt.

Ich erwaehne das hier weil die Folge ein Musterbeispiel dafuer ist, wie man einem nicht-technischen Publikum die ganze Patentproblematik (insbesondere im Zusammenhang mit Softwarepatenten) verstaendlich machen kann. Daher: Ein Muss sowohl fuer alle die gegen den Patentwahnsinn aktiv sind (als Anregung und Referenz) als auch (und insbesondere) natuerlich fuer jene die sich noch nicht so viele Gedanken zu dem Thema gemacht haben.

Besonders gut gefaellt mir, wie in der Sendung aufgezeigt wird, dass Patente in der Welt der tatsaechlich stattfindenden Ereignisse weder innovationstreibenden Firmen noch kleinen Erfindern nutzen, sondern nur einer aeusserst zweifelhaften Industrie von mafiahaft agierenden "Patent Trollen" dabei Hilft eben jene innovationstreibenden Firmen und kleine Erfinder zu terrorisieren.

Derart klar und unmissverstaendlich auf den Punkt gebracht sollte jede ernsthafte Ausseinandersetzung mit dem Thema sein.

Seit etwa eineinhalb Jahren beschaeftigt mich folgender Gedanke. Sicherlich ist der nicht grundlegend neu und daher habe ich mich entschlossen mal darueber zu bloggen. Moeglicherweise hat ja eine mathematisch bewanderte LeserIn einen Pointer zu weiteren Informationen zu dem Thema fuer mich ...

Zunaechst moechte ich den Begriff der "beschreibbaren Zahl" definieren:

Def. 1: Eine beschreibbare Zahl ist eine (reelle) Zahl die entweder ueber eine Beschreibung Ihrer Eigenschaften oder ueber eine Konstruktionsvorschrift innerhalb eines Zeichensystems eindeutig von allen anderen Zahlen unterschieden werden kann.

Man wuerde annehmen, dass alle (reellen) Zahlen in die Menge der beschreibbaren Zahlen fallen. Doch das scheint nicht der Fall zu sein.

Def. 2: Eine Aussage ist eine endliche Folge von Zeichen eines Zeichensystems aus einer endlichen Anzahl von Symbolen, die geeignet ist maximal eine abzaehlbar grosse Menge von konkreten Zahlen zu beschreiben. Z.B. koennte man als Zeichensystem einfach das ASCII-Alphabet und die deutsche Sprache verwenden.

Was ist gemeint mit "maximal eine abzaehlbar grosse Menge von konkreten Zahlen"? Damit ist gemeint, dass eine Aussage zwar z.B. die reellen Zahlen als Menge in ihrerer Gesamtheit beschreiben kann, nicht aber jedes Element eindeutig zu beschreiben vermag. (Selbst mit Auswahlaxiom koennte man wohl nur eine abzaehlbar grosse Teilmenge der reellen Zahlen in einer Aussage beschreiben. Wir wollen das Auswahlaxium aber nicht zulassen, sonst kaeme jemand auf die Idee ein Element aus Menge der nicht beschreibbaren Zahlen auszuwaehlen.) Ich hoffe dieser Sachverhalt ist anschaulich genug so dass er so akzeptiert werden kann.

Lemma 1: Es gibt eine abzaehlbar unendlich grosse Menge von Aussagen. Das folgt unmittelbar, da man jeder Nachricht {z_1, z_2, .. z_n} mit n Zeichen aus einem Zeichensystem aus k verschiedenen Zeichen die natuerliche Zahl sum(z_i * k^(i-1), i = 1..n) zuordenen kann. D.h. man kann z.B. jeder ASCII Datei eine sehr grosse Binaerzahl zuordnen.

Lemma 2: Es gibt eine abzaehlbar unendlich grosse Menge von beschreibbahren Zahlen. Das folgt unmittelbar wenn man Cantors erstes Diagonalargument auf die abzaehlbar unendlich grosse Menge von Aussagen und die abzaehlbar unendlich grosse Menge von beschreibbaren Zahlen pro Aussage anwendet.

D.h. dass es z.B. in der Menge der reellen Zahlen (die ja ueberabzaehlbar groß ist) eine abzaehlbar grosse Teilmenge von beschreibbaren Zahlen gibt zu der alle konkreten Zahlen gehoeren mit denen wir uns je beschaeftigen. Damit wir uns mit einer konkreten Zahl ueberhaupt beschaeftigen koennen muss sie ja beschreibbar sein. Der ueberabzaehlbar grosse Grossteil der reellen Zahlen aber besteht offenbar aus nicht beschreibbaren Zahlen die fuer uns als einzelne nicht greifbar sind. Es ist unmoeglich so eine Zahl aus den reellen Zahlen herauszureissen und als einzelne zu untersuchen.

This blows my mind! Was denkt Ihr?