Pith. sign in

REVIEW 1 cited by

Lossy Catalytic Computation

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2408.14670 v1 pith:N6QJQ3A4 submitted 2024-08-26 cs.CC

Chetan Gupta , Rahul Jain , Vimal Raj Sharma , Raghunath Tewari This is my paper
classification cs.CC
keywords tapeauxiliarycatalyticturingmachinemachinesworkcontent
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

A catalytic Turing machine is a variant of a Turing machine in which there exists an auxiliary tape in addition to the input tape and the work tape. This auxiliary tape is initially filled with arbitrary content. The machine can read and write on the auxiliary tape, but it is constrained to restore its initial content when it halts. Studying such a model and finding its powers and limitations has practical applications. In this paper, we study catalytic Turing machines with O(log n)-sized work tape and polynomial-sized auxiliary tape that are allowed to lose at most constant many bits of the auxiliary tape when they halt. We show that such catalytic Turing machines can only decide the same set of languages as standard catalytic Turing machines with the same size work and auxiliary tape.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum Catalytic Space

    quant-ph 2025-06 reject novelty 8.0 of 10

    Quantum catalytic logspace is claimed to be computable in polynomial time exactly and to simulate TC1 threshold circuits.

Pith tools