Turing Processing

Turing Processor

Turing Programs

Starting in 1985, this hypothetical model of a multitape Turing machine has been developed by A. Schönhage as a medium for an efficient implementation of algorithms dealing with multi-precision data. The TP model has seven tapes for storing data, the underlying alphabet is the set of all 32-bit words for a TP32 (or 16-bit words for a TP16), and the finite control is embodied in some Turing program for a little RISC processor written in assembly language.
The very first implementation was undertaken in 1985/86, running fast integer multiplication on a small MC68000-based machine. Later on, thanks to the programming skills of my coauthors A.F.W. Grotefeld and E. Vetter, we could then establish advanced versions running on SUN workstations and other platforms, with our TP-book plus more recent Addenda as the main reference - also serving as a programmer's guide.

TP Source Modules

The assembly language TPAL is a low level programming language well suited for multi-precision arithmetic modulo the word base & = 2³² of TP32 (= 2¹⁶ for TP16), and to control every detail down to the bit level. Example source file primes.t of a small self-contained program for listing primes may give a first impression. Its compressed version primes.dry without any comment and using anonymous label naming illustrates that such `dry' plaintext can provide some sort of encryption.

Libraries of such TP routines are organized in modules. Chapters 6-9 of the TP-book describe the modules INTARI for integer arithmetic, QARI for rational arithmetic and integer gcd's, RECARI for computing with r-codes and c-codes (binary rationals approximating real and complex numbers), and CREPARI with routines for complex and real polynomials.
Meanwhile we have added many new routines. Due to increased size, module CREPARI had to be split into separate modules CREPAR + CREPEX, and there are now two additional modules PORTA, PORTB containing our new routines for approximate factorization of complex polynomials and approximate computation of polynomial roots.
For documentation of the precise interfacing conditions of the new routines and any updates for the old routines of Chapters 6-9 we are now maintaining so-called docfiles like intardoc etc. as listed at the end of the Addenda. These are pure ASCII-files to provide robust portability.

Availability of Implementations

After E. Vetter had left our team, we had to cope with his tpc compiler (see TP-book Chapter 3) as it was at that time. Because of several difficulties, for instance arising with changes caused by new releases of the GNU compiler `gcc' and other obstacles, the services of Section 3.1.1 (How to get this software) could no longer be maintained, and since my retirement in early 2000 there was simply no manpower to reinstall an operable version of tpc.
To resolve these problems, I decided to write a new implementation of TP32 myself - then called TPS02 (written in 2001/02) - this time as a machine dependent TP-system for Intel's IA-32 Architecture (Pentium II or later, for use of MMX instructions) under GNU-Linux, employing the gcc with its assembler and the GNU Libc. Accordingly this is free software under the terms of the GNU General Public License, see TP-book page 89 for additional conditions as well.

At present there is no implementation of a TP16 - except for my ancient ATARI version, still running on that dusty old machine! - On the other hand, one could wish to use a TP64, in order to exploit the power of modern 64-bit processors, but that would also require substantial modifications in many of our TP routines.
In case somebody wants to implement TP32 for some other platform, s|he may take advantage of the fact that our assembler tpa02, when applied to a TPAL source file XYZ.t, performs a first pass translating this into a module file XYZ.m32 being stored as a sequence of 32-bit words in a machine independent intermediate code. We have designed that m32 format such that it may also serve as a basis for a TP32 in hardware.

TPS02 for IA-32 under GNU Linux

By downloading and unpacking tps02.tar.gz you obtain a directory tpdir/ containing an ASCII-file readme about how to install TPS02, a related makefile, and three subdirectories tpdir/doc/, tpdir/dry/, tpdir/sou/ with these files:

tpdir/doc/
with a brief outline of TPS02 in tps02.pdf,
docfiles intardoc, qardoc, recardoc, crepsdoc, portsdoc,
TP-book related errata.pdf, addenda.pdf,
and License, a copy of the GNU Library General Public License;

tpdir/dry/
with `dry' compressed TP modules intari.t, qari.t,
recari.t, crepar.t, crepex.t, porta.t, portb.t;

tpdir/sou/ with the source files
tpa0.c, tpa2.c for the TP-assembler tpa02,
tpm.c for the startup part tpm.o of any Turing program,
tprun.s for the runtime routines in tprun.o,
demo.t in TPAL, for a little demo example,
tpinit.c for C-function tpinit starting a "TP-server",
expl.t in TPAL, for a little TP-server example.

In case of any problems with this distribution, please contact A. Schönhage

Recent TPS02 (TPS04) news:

July 8, 2005: When used with newer `gcc' versions, the present version of tpm.c (after being gcc compiled to tpm.o needed as the startup part of any Turing program) causes a little problem: When linking tpm.o with tprun.o and some TP-modules like intari.o etc., the gcc may issue a warning about "use of mktemp being dangerous". The following patch in the source file tpm.c settles this:
Replace 8 lines (lines 279-286 of tpm.c , beginning 8 lines after a heading
* tapefile directory */ with k= 100; and ending with
tpfdir: *q++ ='/'; etc.) with these 5 lines:
=============================== p=q= fnum +6; *p-- = 0; /* followed by XXXXXX, and */ do *p='X'; while(p-- > fnum); /* try to make a new direc-*/ if(!mkdtemp(tpf)) /* tory [DIRNAM/]tf??????, */ {err=14; goto errex;} /* error 14 iff this fails */ *q++ ='/'; /* else success: append slash */
===============================
One reason for staying with that older version of tpm.c is, that in old libc versions that function mkdtemp may be missing.
October 27, 2005: This Summer I have finished a new version TPS04 furnishing special back-end coding for Pentium-4 processors, quite analogous to TPS02, obtainable by downloading and unpacking tps04.tar.gz. It improves the TPS02 performance by 30 to 40 percent; for more details, see the corresponding docfile tps04.pdf .
April 10, 2006: A minor bug in the TPS04 release (concerning tracing with unreliable stopping at breakpoints) has been fixed. Accordingly, recompilation of the startup part and the runtime routines from the new source files tpm4.c, tprun4.s is recommended.
September 25, 2006: To illustrate our splitting circle method, we have applied routine MFSP (monic linear factor splitting, cf. item 2.12 of portsdoc) to the polynomial x⁶⁰ - 1 . File split60.dvi provides a graphical report of the main splitting steps and related performance data for this example.
December 13, 2006: We have replaced older preliminary routines for squaring of real and complex polynomials with improved versions (now asymptotically fast also for large degree). To use them, one needs crepar.t, crepex.t from the new tps02.tar.gz or tps04.tar.gz , respectively; see the updated docfile crepsdoc for details and other related new routines.

Some features of TPS02, of TPS04:

Assembly command tpa02 -?? XYZ.t for translating TPAL source XYZ.t admits options ?? to output the intermediate code module XYZ.m32 (also as hex dump XYZ.h32), or to retranslate it to compressed format XYZ.dry; under TPS04, tpa4 replaces tpa02 ;
tpa02, tpa4 support the new directives and commands related to table look-up, as specified in Section 1.2 of the Addenda;
debugging at runtime is supported by a rich repertoire of tracing facilities, like stepping with source code display, setting breakpoints, display of timer accounts, of the stack, dumps of tape segments with decoding support, keyboard interrupts;
large-scale memory supply: besides allocation of m MB in main memory (with m·2¹⁷ bytes per tape), any additional disk space can be accomodated for the Turing tapes (or for the stack) via so-called tapefiles;
to combine some Turing program with other software, typically with some master program written in C or C++, it can be run as a child process; such TP-server receives its input via an INTAPE pipe from the parent process and returns its results via another pipe written by OUTAPE.

Last modified: Wed Apr 16 22:55:07 CEST 2008