測試圖靈機模擬程序

Question

我想爲Java中的圖靈機模擬器程序提出大型測試用例。

程序從輸入文件中讀取數據，並根據測試用例字符串和圖靈機規則列表運行仿真。執行下面的規則後，程序將打印字符串是否被接受，拒絕或不停止給定數量的步驟。

該程序基本上是模擬手動行走在紙上的圖靈狀態機，給定一些輸入字符串。

我發現測試這個程序很困難。該程序適用於所有基礎圖靈機以及相對較小的測試案例。我想測試這個程序給定一個非常大的測試字符串（~30個字符），5000個步驟，以及一些大數量或規則和狀態。

我想知道如果有人能幫我想出一個好的測試案例嗎？

樣品測試案例

7 15 //number of states and number of rules 
0 0 3 B R //[current state, transition character, destination state, value to write, direction to move] 
0 B 2 B R 
0 x 2 x R 
3 x 3 x R 
3 B 1 B R 
3 0 6 x R 
6 x 6 x R 
6 0 4 0 R 
6 B 5 B L 
4 x 4 x R 
4 B 2 B R 
4 0 6 x R 
5 0 5 0 L 
5 x 5 x L 
5 B 3 B R 
3 15 //number of testcases and number of steps to come to a halt 
00 
000 
000000 

提前

Answer 1

非常感謝如果您正在尋找測試用例來進行壓力測試您的實現，你可能想看看busy beaver Turing machines，這是圖靈機具有指定數目的狀態和磁帶符號，這些符號已知在終止之前運行最長的時間。我們知道這些機器完成運行需要多長時間，所以您應該能夠在已知使用大量時間和空間的TM上測試您的模擬器，並確認您的步計數器正常工作。

希望這會有所幫助！