Asking for turing package

General
1

Was intrigued by this SO question, and so I’d like to try implement a Turing machine simulator in pure Prolog. Was thinking to start from some existing code, and attempt to ‘purify’ it, it required. But

?- pack_install(turing).
% Contacting server at https://www.swi-prolog.org/pack/query … ok
Install turing@1.0.2 from https://bitbucket.org/ttmrichter/turing/downloads/turing-1.0.2.tgz Y/n?
ERROR: url `‘https://bitbucket.org/ttmrichter/turing/downloads/turing-1.0.2.tgz’’ does not exist (status(404,Not Found))

Anybody has downloaded the package and could provide it ?

2

It seems that the package was hosted in a Mercurial repository on Bitbucket, which is no longer available, as Bitbucket recently dropped support for Mercurial and deleted all remaining Mercurial repos from their site. Thankfully there are some archives of public Bitbucket Mercurial repos from before they were deleted, such as this one from Software Heritage: https://bitbucket-archive.softwareheritage.org/

You can find the code you’re looking for here: https://bitbucket-archive.softwareheritage.org/projects/tt/ttmrichter/turing.html - either the original Mercurial repo under “Download repository” or the release tarballs (which the pack download URL uses) under “See project downloads”.

3

(1) I remember that I wrote a deterministic turing machine interpreter
in Prolog more than 20 years ago, which is still in pac/prolog/misc/turing.pl
of my package pac as a toy programming. It works as CGI in Japanese

As it is not for non-deterministic TM, it would be useless for your purpose.

(2) Although it is not related to Prolog but to Java (?), the following is
a book on ND TM.

Turing’s World 3.0 for Mac: An Introduction to Computability Theory (Center for the Study of Language and Information Publication Lecture Notes)
Jon Barwise, John Etchemendy

5

Got it, thanks so much!

I thought that deterministic machines were all we needed to demonstrate Turing completeness… I’m wrong ?

Have tried to read the article, but it’s beyond my math level. Even the Example 3 it’s hard to relate to the problem at hand. Thanks anyway…

7

Yes.

Once I was a little bit familiar with following well-known results,
though most details of which have already gone from my head.

The following computatability platforms are equivalent

lambda calculus
Turing machine (NDTM/DTM)
General recursive function
Post machine
Chomsky’s type 0 grammar
(… possibliy many others)

1 Like