Oft wird der Nachweis, dass das Halteproblem nicht entscheidbar ist, in der Fachliteratur (Schöning [📖Sch08, 119 f.], Asteroth und Baier [📖BA02, 106 f.], Sipser [📖Sip12, 216 f.]) mithilfe einer Turingmaschine und einem Widerspruchsbeweis gezeigt, in etwa:

Angenommen,

ist entscheidbar.

Sei $T'$ ist die Turingmaschine, die $K'$ entscheidet.
Sei $w = \langle T \rangle$ die Codierung¹ einer Turingmaschine, die wie folgt arbeitet:

• $T$ simuliert das Verhalten von $T'$ bei der Eingabe $w$:
  • $T$ stoppt, wenn $T'$ die Eingabe $w$ verwirft ($w \notin K'$)
  • $T$ stoppt nicht, wenn $T'$ die Eingabe $w$ akzeptiert ($w \in K'$)

Damit folgt: $T$ stoppt bei Eingabe $w$ $\Leftrightarrow$ $T'$ verwirft $w$ $\Leftrightarrow$ $w \notin K'$ $\Leftrightarrow$ $T$ stoppt nicht

Widerspruch!

Für das Modul prog[^1] im Wintersemester 2023/2024 des Fernstudiengangs Informatik (M.C.Sc.) der Hochschule Trier habe ich hier Lösungshinweise zu ausgewählten Tests zusammengefasst. Diese stehen als PDF zum Download zur Verfügung.

Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als Sortieren mit abnehmenden Inkrementen [📖OW17b, 88], das Verfahren ist eine Variation von Insertion Sort:

[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, 48]

In der vorliegenden Implementierung (siehe Listing 1) werden $t = log_2(n)$ Inkremente[^1] $h_t$[^2] der Form $\lfloor {\frac{n}{2^i}} \rfloor$ verwendet, um $lg(n)$ $h$-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in $h_1$ die Schlüssel mit Abstand=$1$.

Die Effizienz des Sortierverfahrens ist stark abhängig von $h$: So zeigt Knuth, dass $O(n^{\frac{3}{2}})$ gilt, wenn für $h$ gilt: $h_s = 2^{s+1} - 1$ mit $0 \leq s < t = \lfloor{lg(n)} \rfloor$ (vgl. [📖Knu97c, 91][^3]. In unserem Fall können wir von $O(n^2)$ ausgehen.

Man darf behaupten, dass im Jahr 2023 das Thema Künstliche Intelligenz endgültig in der Gesellschaft angekommen ist. Mit der Veröffentlichung von ChatGPT Ende 2022 ist "KI" plötzlich für jeden begreifbar. Einmal mehr rutschen defätistische Prophezeiungen auf die Titelseiten der Boulevard-Presse.

Als Software Entwickler mit Schwerpunkt Design und Architektur hatte ich Künstliche Intelligenz bis dahin weitestgehend in den akademischen Bereich verortet.

Dann hatte ich das Glück, mich ausgiebig mit Künstlicher Intelligenz im Rahmen meiner Zulassungsarbeit für den Fernstudiengang Informatik (M.C.Sc.) an der Hoschschule Trier beschäftigen zu dürfen.

Entstanden ist eine Arbeit, in dem ich mathematische Modelle künstlicher Neuronen vorstelle. Auf dem Weg dorthin bin ich in die frühen Anfänge der Neurowissenschaft, der Kybernetik und Rechnerarchitektur eingetaucht. Es hat meine Sichtweise auf vieles, was mir bis dahin (un)verständlich gewesen ist, geändert.

I have updated my Perceptron-implementation with a plotting function that allows for visualizing the adjustments of the Perceptron's weight-vector through the epochs.

The source-code can be found at https://github.com/ThorstenSuckow/pylabs.

Usage​

Create input data and the associated output values. As an example, the following represents the logical AND-function:

Errata für Beweisen lernen (Springer Verlag 2020) von Junk und Treude. Ich hoffe, dass meine Notizen dem Autorenteam zur Überprüfung und ggf. Korrektur nützlich sind.

Zum Hintergrund dieses Blog-Posts gibt es weiter unten mehr Informationen.

Verfällt ein Big Ball of Mud?​

Durch den Fortschritt der Technologie und der Arbeit von Leuten wie Brooks, Buschmann und Booch wurde uns Entwicklern der Weg vom mikroskopischen ins makroskopische geebnet. Lang vorbei sind die Zeiten, in denen schrankhohe Rechnersysteme nah an der Infrastruktur programmiert werden mußten.
Jedoch, wer heute den Mythischen Mann-Monat [📖MMM] liest und über die damals zur Verfügung stehende Technik schmunzelt, der wird spätestens bei der Aktualität der anderen erwähnten Probleme betreffs Organisation und Planung von Projekten rasch in die Gegenwart zurückgeworfen. Aus Eskapismus wird ein erhobener Finger: Das Lesevergnügen mahnt plötzlich zur Reflektion. Die Probleme von damals sind heute immer noch aktuell, und die Entwicklung der Technik verlief bis dato offensichtlich ungleich schneller als die von Planung und Organisation.

bcc-header issues with Horde_Mime_Mail​

This issue caused some uncertainty since I was not sure if the headers were broken due to missing quotes. See https://github.com/conjoon/php-lib-conjoon/issues/17.

Turns out that the way I assembled an email from a full text and converting it back to an instance of Horde_Mime_Mail does not consider the type of the internal representation of the bcc-field properly. It's related to Horde_Mail_Rfc822_List::_normalize and how values passed from Horde_Mime_Mail::send() are processed by it.

Fix: Missing favicon.ico in Sencha ExtJS production builds​

Fixing missing favicon.ico in Ext JS applications.

The original issue is tracked here: https://github.com/conjoon/conjoon/issues/24

The issue​

I’m not quite sure *when *and *why *it broke, but it looks like production builds of Sencha Ext JS applications do not contain any favicon.ico originally existing in the development build (anymore).

Releasing conjoon V1.0​

I’m happy to announce conjoon 1.0, the very first major release of the Open Source JavaScript Email client.

For updating to the latest version, simply use our installer. It will let you select the latest release when opting for the version to install.