ในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีบทการเร่งความเร็วเชิงเส้นสำหรับเครื่องจักรทัวริงระบุว่า เมื่อกำหนดc  > 0 จริง ใดๆ และ เครื่องจักรทัวริงแบบk เทปใดๆ ที่แก้ปัญหาในเวลา f ( n ) จะมี เครื่องจักร แบบ kเทปอีกเครื่องหนึ่งที่แก้ปัญหาเดียวกันในเวลาไม่เกินf ( n )/ c + 2n + 3โดยที่k  > 1 ^{[ 1 ] [ 2 ]} หากเครื่องจักรเดิมไม่ใช่แบบกำหนดได้เครื่องจักรใหม่ก็จะไม่ใช่แบบกำหนดได้เช่นกัน ค่าคงที่ 2 และ 3 ใน 2n + 3 สามารถลดลงได้ เช่น เป็นn + 2 ^{[ 1 ]}

ทฤษฎีบทนี้ยังใช้ได้กับเครื่องจักรทัวริงที่มี เทปอินพุตแบบ อ่านอย่างเดียว ทางเดียว และเทปทำงานด้วย^{[ 3 ]}${\displaystyle k\geq 1}$

สำหรับเครื่องทัวริงแบบเทปเดี่ยว การเร่งความเร็วเชิงเส้นจะใช้ได้กับเครื่องที่มีเวลาดำเนินการอย่างน้อยพิสูจน์ได้ว่าไม่ใช้ได้กับเครื่องที่มีเวลา^{[ 3 ]}${\displaystyle n^{2}}$${\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})}$

โครงสร้างนี้อาศัยการบรรจุสัญลักษณ์เทปหลายๆ ตัวจากเครื่องเดิมMลงในสัญลักษณ์เทปเดียวของเครื่องใหม่Nซึ่งมีผลคล้ายกับการใช้คำและคำสั่งที่ยาวขึ้นในโปรเซสเซอร์ กล่าวคือ ช่วยเพิ่มความเร็วในการคำนวณ แต่ก็เพิ่มขนาดของเครื่องด้วย จำนวนสัญลักษณ์เดิมที่บรรจุลงในสัญลักษณ์ใหม่นั้นขึ้นอยู่กับความเร็วที่ต้องการเพิ่มขึ้น

สมมติว่าเครื่องจักรใหม่บรรจุสัญลักษณ์เก่าสามตัวลงในสัญลักษณ์ใหม่หนึ่งตัว ดังนั้นตัวอักษรของเครื่องจักรใหม่จะเป็นดังนี้: ประกอบด้วยสัญลักษณ์เดิมและสัญลักษณ์ที่บรรจุแล้ว เครื่องจักรใหม่มีจำนวน เทป k  > 1 เท่าเดิม สถานะของNประกอบด้วยส่วนประกอบต่อไปนี้: ${\displaystyle \Sigma \cup \Sigma ^{3}}$

• สถานะของM ;
• สำหรับเทปแต่ละม้วน จะมีสัญลักษณ์ที่บรรจุอยู่สามแบบ ซึ่งอธิบายถึงสัญลักษณ์ที่บรรจุอยู่ใต้หัวอ่าน สัญลักษณ์ที่บรรจุอยู่ทางด้านซ้าย และสัญลักษณ์ที่บรรจุอยู่ทางด้านขวา และ
• สำหรับเทปแต่ละม้วน ตำแหน่งหัวอ่านเดิมจะอยู่ภายในสัญลักษณ์ที่บรรจุอยู่ใต้หัวอ่านของN

เครื่องจักรใหม่Nเริ่มต้นด้วยการเข้ารหัสข้อมูลป้อนเข้าที่กำหนดลงในตัวอักษรใหม่ (นั่นคือเหตุผลที่ตัวอักษรของมันต้องมี) ตัวอย่างเช่น หากข้อมูลป้อนเข้าของเทป 2 ม้วนMอยู่ทางด้านซ้าย หลังจากเข้ารหัสแล้ว การจัดเรียงเทปของNจะอยู่ทางด้านขวา: ${\displaystyle \Sigma }$

[ #

_

เอ

ข

ข

เอ

ข

ข

เอ

_

...]

[ #

(_,_,_)

(_,_,_)

(_,_,_)

...]

[ #

_

_

_

_

_

_

_

_

_

...]

[ #

(_,a,b)

(บ, อะ, บ)

(b,a,_)

...]

เครื่องใหม่จะบรรจุสัญลักษณ์เก่าสามตัว (เช่น สัญลักษณ์ว่าง_ , สัญลักษณ์aและสัญลักษณ์b ) ลงในสัญลักษณ์ใหม่ (ในที่นี้คือ (_, a , b )) แล้วคัดลอกไปยังเทปที่สอง พร้อมกับลบข้อมูลในเทปแรก เมื่อการเริ่มต้นเสร็จสิ้น เครื่องใหม่จะหันหัวอ่านไปยังจุดเริ่มต้น โดยรวมแล้ว กระบวนการนี้ใช้เวลา 2 n + 3 ขั้นตอน

หลังจากการเริ่มต้นระบบ สถานะของNคือโดยที่สัญลักษณ์หมายความว่าเครื่องจะเติมข้อมูลลงไปในภายหลัง สัญลักษณ์หมายความว่าหัวของเครื่องเดิมชี้ไปยังสัญลักษณ์แรกภายในและตอนนี้เครื่องจะเริ่มจำลอง การเปลี่ยนสถานะของ M จำนวน m = 3 ครั้งโดยใช้การเปลี่ยนสถานะของตัวเอง 6 ครั้ง (ในกรณีนี้ จะไม่มีการเร่งความเร็ว แต่โดยทั่วไปmอาจมีค่ามากกว่า 6 มาก) ให้การกำหนดค่าของMและNเป็นดังนี้: ${\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])}$${\displaystyle ?}$${\displaystyle [1,1]}$${\displaystyle (\_,\_,\_)}$${\displaystyle (\_,a,b)}$

[ #

_

_

ข

ข

เอ

ข

ข

เอ

_

...]

[ #

(_,a,b)

(บ, อะ, บ)

( b ,_,_)

...]

[ #

_

เอ

ข

ข

เอ

ข

ข

_

_

...]

[ #

(_,_, b )

(บ, อะ, บ)

(b,a,_)

...]

โดยสัญลักษณ์ที่เป็นตัวหนาแสดงตำแหน่งหัว สถานะของNคือต่อไปนี้จะเกิดขึ้น: ${\displaystyle (q;~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

• เครื่องจักร Nเคลื่อนที่ไปทางขวา ซ้าย ซ้าย ขวา หลังจากเคลื่อนที่ครบสี่ครั้ง เครื่องจักรNจะเติมเต็มทุกช่องและสถานะของมันจะเป็นดังนี้${\displaystyle ?}$${\displaystyle (q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])}$
• ตอนนี้Nจะอัปเดตสัญลักษณ์และสถานะตาม การเปลี่ยนสถานะ m = 3 ครั้งของเครื่องจักรดั้งเดิม ซึ่งอาจต้องใช้การเคลื่อนไหวสองครั้ง (อัปเดตสัญลักษณ์ปัจจุบันและอัปเดตสัญลักษณ์ที่อยู่ติดกันหนึ่งตัว) สมมติว่าเครื่องจักรดั้งเดิมเคลื่อนไหวดังต่อไปนี้ (โดยมีการกำหนดค่าที่สอดคล้องกันของNทางด้านขวา):

[ #

_

_

_

_

_

ข

ข

เอ

_

...]

[ #

(_,a,b)

( b ,_,_)

(_,_,_)

...]

[ #

_

เอ

ข

ข

_

_

_

_

_

...]

[ #

(_,_,_)

(_,_, b )

(b,a,_)

...]

ดังนั้น สถานะของNจึงกลายเป็น. ${\displaystyle (q';~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

การเริ่มต้นต้องใช้ 2n + 3 ขั้นตอน ในการจำลอง ขั้นตอนN จำนวน 6 ขั้นตอน จะจำลอง ขั้นตอน Mจำนวนm ขั้นตอน การเลือกm > 6c จะทำให้เวลาในการทำงานถูกจำกัดด้วย${\displaystyle f(n)/c+2n+3.}$

การพิสูจน์ทฤษฎีความเร็วขึ้นอยู่กับความสามารถในการบีบอัดพื้นที่จัดเก็บโดยการแทนที่ตัวอักษรด้วยตัวอักษรที่ใหญ่กว่า โดยเฉพาะอย่างยิ่ง ขึ้นอยู่กับทฤษฎีการบีบอัดเทป : ^{[ 4 ] : ทฤษฎีบท 2.1, 2.2}

ถ้าภาษาใดได้รับการยอมรับโดยเครื่องทัวริงภายในปริภูมิแล้วสำหรับค่าใดๆ ก็ตามจะต้องมีเครื่องทัวริงบางเครื่องที่ยอมรับภาษานั้นภายในปริภูมิเช่นเดียวกันนี้ก็ใช้ได้กับเครื่องทัวริงแบบไม่กำหนดด้วย${\displaystyle L}$${\displaystyle s(n)}$${\displaystyle c>0}$${\displaystyle c\cdot s(n)}$

สำหรับเครื่องทัวริงเทปเดี่ยวที่ไม่กำหนดซึ่งมีความซับซ้อนของเวลาสามารถเร่งความเร็วเชิงเส้นได้โดยไม่ต้องเพิ่มตัวอักษร^{[ 5 ]}${\displaystyle T(n)\geq n^{2}}$

Regan ^{[ 6 ]}พิจารณาคุณสมบัติของแบบจำลองการคำนวณที่เรียกว่าความใกล้เคียงของข้อมูล คุณสมบัตินี้เกี่ยวข้องกับโครงสร้างหน่วยความจำ: เครื่อง Turing มีความใกล้เคียงเชิงเส้น ในขณะที่เครื่อง Kolmogorov-Uspenskiiและเครื่องชี้ อื่นๆ มีความใกล้เคียงแบบเลขชี้กำลัง วิทยานิพนธ์ของ Regan คือการมีอยู่ของความเร็วเชิงเส้นเกี่ยวข้องกับการมีความใกล้เคียงของข้อมูลแบบพหุนาม จุดสำคัญในข้ออ้างนี้คือแบบจำลองที่มีความใกล้เคียงแบบเลขชี้กำลังจะไม่มีความเร็วเพิ่มขึ้นแม้ว่าจะอนุญาตให้เปลี่ยนตัวอักษรได้ (สำหรับแบบจำลองที่มีหน่วยความจำแบบไม่ต่อเนื่องที่เก็บสัญลักษณ์) อย่างไรก็ตาม Regan ไม่ได้พิสูจน์ทฤษฎีบททั่วไปใดๆ ในลักษณะนี้ Hühne ^{[ 7 ]}พิสูจน์ว่าหากเราต้องการให้ได้ความเร็วเพิ่มขึ้นจากการจำลองแบบออนไลน์ (ซึ่งเป็นกรณีสำหรับความเร็วเพิ่มขึ้นบนเครื่อง Turing ทั่วไป) ความเร็วเชิงเส้นจะไม่มีอยู่บนเครื่องที่มี การจัด เก็บ แบบต้นไม้