I was searching for a simple way of experimenting with Turing machines for a small course I will give, but most of the software out there is either too complicated or has restrictions, like a predefined alphabet. So I hacked together a small turing machine:

(defun run-turing-machine
  (statelist current-state-name band bandptr)
   (let* ((bandlen (length band))
	  (cstate (cdr (assoc current-state-name statelist)))
	  (calpha (elt band bandptr))
	  (cdo (cdr (assoc calpha cstate)))
	  (do-write (car cdo))
	  (do-move (cadr cdo))
	  (do-goto (caddr cdo)))
     (setf (elt band bandptr) do-write)
     (incf bandptr (cond ((eql do-move 'R) 1)
                         ((eql do-move 'L) -1)
                         ((eql do-move 'S) 0)))
     (dotimes (i 70)
       (format t "~d" (elt band (+ i bandptr -35))))
     (format t "~%")
     (if (eql do-goto 'HALT) nil
	 (run-turing-machine statelist do-goto band bandptr))))

As it is very short, it is very easy to customize, so maybe it is the right thing for other people who are able to use lisp and want something similar. Which is why I am blogging about it, even though it is nothing special.

The code should be self-explanatory, as an example, the following is a machine which increases a dual number (consisting of 0s and 1s, bounded by 2 in the beginning and 3 in the end), and its output:

(run-turing-machine 
 '(
  (anf (0 2 S HALT) (1 2 S HALT) (2 2 R zu3))
  (zu3 (0 0 R zu3) (1 1 R zu3) (3 3 L letzteziffer))
  (letzteziffer (0 1 L andenanf) (1 0 L letzteziffer) (2 1 L anf))
  (andenanf (0 0 L andenanf) (1 1 L andenanf) (2 2 S HALT))
 )
 'anf
 (make-array '(100) :initial-contents
 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 3 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 50)

0000000000000000000000000000000000211111300000000000000000000000000000
0000000000000000000000000000000002111113000000000000000000000000000000
0000000000000000000000000000000021111130000000000000000000000000000000
0000000000000000000000000000000211111300000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000021111130000000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000000211110300000000000000000000000000000000
0000000000000000000000000000000021110030000000000000000000000000000000
0000000000000000000000000000000002110003000000000000000000000000000000
0000000000000000000000000000000000210000300000000000000000000000000000
0000000000000000000000000000000000020000030000000000000000000000000000
0000000000000000000000000000000000001000003000000000000000000000000000
0000000000000000000000000000000000021000003000000000000000000000000000

Na also es geht doch: Eine dreizehnjährige die im Internet sexuell belästigt wurde hat dies zur Anzeige gebracht.

Zitat: “So muss es laufen“, sagte ein Sprecher.

Ja, das ist genau das was ich mich so oft frage. Man sagt seinen Kindern auch, dass sie nicht zu Fremden ins Auto steigen sollen, und auch nicht mit Fremden mitgehen sollen. Wieso kann man ihnen nicht auch so einen Umgang mit dem Internet beibringen?

Es ist doch wirklich nicht so schwer: Wenn dich jemand belästigt sag es weiter, sag niemandem deine Adresse, und treffe dich nie mit jemanden den du nur aus dem Internet kennst ohne Begleitung. Einfache Regeln, die das Netz wirklich sicherer machen. Und das ohne Zensurmaßnahmen und Vorratsdatenspeicherung.

Ich frage es mich immer wieder. Die Programmierung scheint immernoch als akademische Disziplin zu gelten. Dabei regen sich die Leute immer wieder auf, dass das Informatik-Studium zu theoretisch dafür ist. Ich meine damit nicht die Elfenbeinturmschwingereien zwischen den theoretischen Informatikern und denen die die Informatik als reine Ingenieurswissenschaft ansehen, ich sehe hier den klaren Unterschied zwischen Fachinformatik die man an einer FH lernt und universitärer Informatik. Nein, ich meine damit das bloße Programmieren als solches.

Wieso ist "Programmierer" kein Handwerk, wie Bäcker, Maurer, Friseur? So normal mit Ausbildung, Meisterbrief, etc.? Man würde damit einen Haufen Nervensägen von der Uni fernhalten, andererseits einem Haufen von Real- und Hauptschülern eine zusätzliche Berufschance geben, die garnicht so schlecht ist.

Was muss man als Programmierer tun? Wohl in erster Linie implementieren was Andere einem sagen. Die Programmierarbeiten erledigen, die sonst keiner machen will. Klar, das ist das Los der Handwerker, man muss auch mal Drecksarbeit machen (ist aber auch im akademischen Bereich nicht anders, sieht nur etwas anders aus). Was muss man dafür können?

Sicherlich ist die Kenntnis von mehreren Programmiersprachen und Software-Systemen notwendig. Das Wissen um effiziente Algorithmen ebenfalls. Ein wenig Theorie ist sicher auch nicht schlecht, allerdings kann man das sehr weit herunterschrauben, denn das meiste Theoretische kann man (Fach)Informatikern überlassen.

Programmieren kann man jedenfalls gut in Eigenregie lernen, und die notwendigen Kenntnisse, um im unternehmerischen Bereich Fuß zu fassen, kann man wohl am Besten in Unternehmen lernen. Es wäre eigentlich ein hervorragender Handwerksberuf. Mir ist aber nicht bekannt, dass es einen solchen gibt.

W00t. Soon there will be eatable tomatoes! Remember that the whole plant looked like this in the begining, and like this halfways. Now it looks like this:

Awesome!

Again, just a short post with a link. Sorry for that:

This video is the beginning of an amusing game the "Stupid Mario Bros." (I already linked in my former blog) produced.

Zur Zeit gibts von mir leider seltener längere Texte. Dafür aber vielleicht ein paar Links. Zum Beispiel zu diesem Artikel über Visionen. Passt ganz gut zu dem was ich dereinst über Pragma-Idealismus geschrieben habe. Und vielleicht zu diesem SMBC-Comic.

I forgot to throw away the rest of my noodle soup a few days ago. The result was not as gross as I expected. It resulted in an interesting structure:

At least the ext[2-4] filesystems support files with holes. They can be created in several ways, one possibility is the seek-argument of the dd command:

$ dd if=/dev/urandom of=test bs=4096 count=10 seek=10
10+0 records in
10+0 records out
40960 bytes (41 kB) copied, 0.0126733 s, 3.2 MB/s
$ wc -c test
81920 test

So I was interested in whether it is possible to actally find these holes. ZFS and XFS have their own API for that.

For ext*, there is also a possibility to find holes. Basing on the FIBMAP Ioctl (and similar), you need to have the CAP_SYS_RAWIO capability (that is, usually you have to be root). If you only want to watch the holes in the files, you can use for example hdparm (as shown here):

$ sudo hdparm --fibmap test

test:
 filesystem blocksize 4096, begins at LBA 0; assuming 512 byte sectors.
 byte_offset  begin_LBA    end_LBA    sectors
       40960    8928120    8928199         80

Another possibility is to use the filefrag-utility, which is contained in the debian squeeze package e2fsprogs (as shown here):

$ sudo filefrag -v test
Filesystem type is: ef53
File size of test is 81920 (20 blocks, blocksize 4096)
 ext logical physical expected length flags
   0      10  1116015              10 eof
test: 2 extents found

Now if you really want to use your own program, here is a nice example code I found, on which I based my own code:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <linux/fs.h>


int main (int argc, char* argv[]) {
  int fd, blocknum, blocksize;
  struct stat fileinfo;

  if (argc < 1) {
    fprintf(stderr, "Syntax Errof\n");
    exit(EXIT_FAILURE);
  }

  if ((fd = open(argv[1], O_RDONLY)) < 0) {
    int errnum = errno;
    fprintf(stderr, "Cannot open '%s': %s\n", argv[1], strerror(errnum));
    exit(EXIT_FAILURE);
  }

  if (ioctl(fd, FIGETBSZ, &blocksize) < 0 ) {
    int errnum = errno;
    fprintf(stderr, "Cannot get blocksize: %s\n", strerror(errnum));
    exit(EXIT_FAILURE);
  }

  if (fstat(fd, &fileinfo) < 0) {
    int errnum = errno;
    fprintf(stderr, "Stat failed: %s\n", strerror(errnum));
    exit(EXIT_FAILURE);
  }

  blocknum = (fileinfo.st_size + blocksize - 1) / blocksize;

  printf("Filename: %s\nBlocksize: %d\nBlocknum: %d\n",
         argv[1], blocksize, blocknum);
 
  int i;
  for (i = 0; i < blocknum; i++) {
    int block = i;
    if (ioctl(fd, FIBMAP, &block)) {
      printf("ioctl failed: %s\n", strerror(errno));
    }
    printf("%10d\t", block);
  }
  close(fd);
  printf("\n");
  exit(EXIT_SUCCESS);
}

The output:

$ sudo ./fibmap test
Filename: test
Blocksize: 4096
Blocknum: 20
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
   1116015
   1116016
   1116017
   1116018
   1116019
   1116020
   1116021
   1116022
   1116023
   1116024

And that is indeed a list of ten null-pointers and ten consecutive blocks.