// Arup Guha
// 10/23/2024
// Code to go along with the proof that shows ETM is undecidable via reduction
// We assume ETM is decidable, and with it, show how to solve ATM.

import java.util.*;

public class reduction {

	// Pretend this is M this is given to me as well as w, say w= 22 or 23...
	// as an instance of ATM...
	public static boolean isPrime(int n) {
	
		if (n<2) return false;
		
		// typical primality check code.
		for (int i=2; i*i<=n; i++)
			if (n%i == 0)
				return false;
				
		return true;
	}
	
	// Someone has asked me if isPrime will accept 23....
	
	// M2 is building this machine. Then M2 will pass this function as a parameter to
	// M1... In this reduction mPrime is designed to accept nothing or w. It will accept
	// w is M accepts w.
	public static boolean mPrime(int n) {
	
		// Hard-coded to reject anything that isn't equal to w...I put in 22 for now.
		if (n != 22) return false;
		
		/*** Copy paste regular isPrime code. ***/
		
		if (n<2) return false;
		
		for (int i=2; i*i<=n; i++)
			if (n%i == 0)
				return false;
				
		return true;	
	}
	
	// Language of mPrimeAlternate is either empty set, or sigma star...
	public static boolean mPrimeAlternate(int n) {
	
		// Overwrite input with w.
		n = 23;
		
		/*** Run regular code on w regardless of what n is set to. Here I've used w=23. ***/
		if (n<2) return false;
		
		for (int i=2; i*i<=n; i++)
			if (n%i == 0)
				return false;
				
		return true;	
	}
	
	// Just did this so you can see that the "language" of both mPrime and mPrimeAlternate
	// can be used to deduce whether or not M accepts w or not. L(mPrime) = emptyset or {w}.
	// L(mPrimeAlternate) = emptyset or sigma*.
	public static void main(String[] args) {
	
		for (int i=0; i<100; i++)
			if (mPrimeAlternate(i))
				System.out.println("mPrime accepted "+i);
	
	}
}