Classical Computability - Part 3 (of 3) (String Computability)

(Part 3)

Purpose of this part is first to extend the formalized notions of computability to the domain of arbitrary strings of symbols of an alphabet.  In 3.1 computable bijections from alphabets A to N are introduced. These have the features of allowing homogeneous base n notations for positive integers, for all n>0 and the encoding and decoding by means of p.r. functions. Several useful properties of the coding functions are derived.

In 3.2 definitions extending the formalized computability concepts to the domain of strings are given first. Then some important string functions and relations are proved to be recursive. These are used in the subsequent sections for equivalence proofs.

In Sections 3.3 – 3.5 different kinds of string manipulating algorithms are introduced and proved equivalent, including Post-Turing programs (Section 3.4), as well as deterministic and nondeterministic quintuple and quadruple Turing programs (3.5). The operational semantics of the latter was approximated to the other languages occurring in this work. The uncomplicated equivalence proofs in 3.5.2 come from the present author. Part 3 is here in pdf-Format.





3           Computations on strings (Words)


3.1        Effective denumerability of strings
3.2        String computability


3.3        The programming languages L
3.3.1     The syntax of L
3.3.2     The semantics of L
3.3.3     Some useful macros in L
3.3.4     Simulation of R in L


3.4        The programming language P (Post-Turing programs)
3.4.1     The syntax of P
3.4.2     The semantics of P
3.4.3     Some useful macros in P
3.4.4     Simulation of L in P
3.4.5     Simulation of P in R


3.5        Deterministic and nondeterministic Turing programs
3.5.1     The programming languages T4 and T5
3.5.1.1   Syntax
3.5.1.2   Semantics  
3.5.2      Simulations of P in T5, T5 in T4, and T4 in P