scientific article; zbMATH DE number 4049059

zbMATH Open0643.68066MaRDI QIDQ3785950FDOQ3785950

Authors: Shigeki Iwata, Takumi Kasai 

Publication date: 1987

Title of this publication is not available (Why is that?)

Recommendations

• Simultaneous (poly-time, log-space) lower bounds
• Most programs stop quickly or never halt
• Asymptotic proportion of hard instances of the halting problem
• A note on simple programs with two variables
• A statistical anytime algorithm for the halting problem

zbMATH Keywords

Turing machinehalting problemsimple programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Cited In (1)

• A note on simple programs with two variables

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785950)