English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the 1960's Gisbert Hasenjaeger built Turing Machines fromelectromechanical relays and uniselectors. Recently, Glaschick reverseengineered the program of one of these machines and found that it is auniversal Turing machine. In fact, its program uses only four states and twosymbols, making it a very small universal Turing machine. (The machine hasthree tapes and a number of other features that are important to keep in mindwhen comparing it to other small universal machines.) Hasenjaeger's machinesimulates Hao Wang's B machines, which were proved universal by Wang.Unfortunately, Wang's original simulation algorithm suffers from an exponentialslowdown when simulating Turing machines. Hence, via this simulation,Hasenjaeger's machine also has an exponential slowdown when simulating Turingmachines. In this work, we give a new efficient simulation algorithm for Wang'sB machines by showing that they simulate Turing machines with only a polynomialslowdown. As a second result, we find that Hasenjaeger's machine alsoefficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger'smachine is both small and fast. In another application of our result, we showthat Hooper's small universal Turing machine simulates Turing machines inpolynomial time, an exponential improvement.

Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy